计算不在List<；int>；

本文关键字：int gt lt List 计算 | 更新日期: 2023-09-27 18:28:37

我有一个很短的List<int>:

var list = new List<int> {0, 4, 1, 3};

列表未排序
我需要找到最低的整数，从0开始，它不属于列表
目前我使用以下算法：

int x = 0;
while (list.Contains(x))
   x++;
// In this example it must be: x = 2

该算法非常简单，但它不是线性O（n），我需要使用不同的列表多次计算这个值。

如何加快这种方法的速度？

计算不在List<；int>；

在不了解太多实际限制的情况下，这可能是一个解决方案：

int breakpoint = 153; // Or whatever number you've  found is the breakpoint
int FirstMissingNumber(List<int> list)
  IEnumerable<int> toIterateOver = list;
  if (list.Count > breakpoint)
    toIterateOver = new HashSet<int>(list);
  int i = 0;
  while (toIterateOver.Contains(i))
   i++;
  return i;
}

不过要注意，对于较小的列表，创建哈希集的开销肯定大于Contains()上的O(1)速度增益。

编辑：添加了一个断点"开关"，您必须手动查找断点在环境中的位置。

为什么不像下面的那样对列表进行排序并循环查找缺失的数字

        var list = new List<int> { 0, 4, 1, 3 };
        list.Sort();
        for (int i = 0; i < list.Count; i++)
        {
            if (!list.Contains(i))
            {
                Console.WriteLine("Missing {0}", i);
                break;
            }
        }
相关文章：