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

Question

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

List<int> myInts = new List<int>();

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中的第一个元素不包含在myInts:

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

编辑以回应评论:

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

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