确定整数列表中的第一个可用值

我得到了一个简单的整数列表。

List myInts = new List(); myInts.Add(0); myInts.Add(1); myInts.Add(4); myInts.Add(6); myInts.Add(24); 

我的目标是从List中获取第一个未使用的（可用）值。

（集合中尚未出现的第一个正值）

在这种情况下，答案是2。

这是我目前的代码：

 int GetFirstFreeInt() { for (int i = 0; i < int.MaxValue; ++i) { if(!myInts.Contains(i)) return i; } throw new InvalidOperationException("All integers are already used."); } 

有没有更好的办法？ 也许使用LINQ？ 你会怎么做？

当然，我在这里使用了简单但我的问题适用于任何类型。

Answer 1

您基本上需要0..int.MaxValue中未包含的序列0..int.MaxValue中的第一个元素：

 int? firstAvailable = Enumerable.Range(0, int.MaxValue) .Except(myInts) .FirstOrDefault(); 

编辑以回应评论：

迭代到int.MaxValue 没有性能损失。 Linq将在内部创建一个哈希表，然后开始迭代由Enumerable.Range()创建的序列 – 一旦哈希表中未包含的第一个项被发现整数由Except()方法产生，由FirstOrDefault()返回 – 之后迭代停止。 这意味着整体努力是O（n）用于创建散列表，然后是最坏情况O（n）用于迭代序列，其中n是myInts的整数myInts 。

有关Except()更多信息，请参阅Jon Skeet的EduLinq系列： 重新实现对象的LINQ：第17部分 – 除外

Answer 2

好吧，如果列表从最小到最大排序并包含从0到正无穷大的值，您可以简单地访问第i个元素。 if (myInts[i] != i) return i; 它本质上是相同的，但不需要遍历列表中的每个Contains检查（Contains方法遍历列表，将算法转换为O（n平方）而不是O（n））。