C# 以 int 数组作为索引过滤循环的更快方法？

Question

抱歉，如果这是重复的，第一个问题...

我想对大量称为注释的结构进行操作。但我不想对笔记的每个元素进行操作。我正在尝试使用 int 数组 (int[]) 的 filter 来跳过其中的很多内容，如下面的代码所示。

Note[] notes = new Note[]
{ 
   // Struct stuff ... 
};

int[] filter = new int[]{ 4,20,50,367... };

for (int i = 0; i < notes.Length; i++)
{
     bool flag = false;
     for (int j = 0; j < filter.Length; j++)
     {
          if (i == filter[j])
          {
               flag = true;
               break;
          }
      }

      if (flag) continue;
      // Do something on notes[i]
}

问题是，当注释数组和过滤器数组都扩展时，代码将运行非常慢(我认为)。那么，是否有更好、更快的方法来做到这一点？请注意，过滤器的大小可以是基于其他条件的任何大小

Answer 1

我们可以在 HashSet<int> 的帮助下摆脱内部循环同时拥有更好的O(|filter| + |notes|) 时间复杂度 而不是初始的 O(|filter| * |notes|) :

Note[] notes = new Note[] { 
  ... //Struct stuff 
};

int[] filter = new int[] { 
  4, 20, 50, 367... 
};

HashSet<int> toExclude = new HashSet<int>(filter);

for (int i = 0; i < notes.Length; i++) {
  if (toExclude.Contains(i)) // O(1) time complexity 
    continue;

  //Do something on notes[i] 
}