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

Question

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

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

myInts.Add(0);
myInts.Add(1);
myInts.Add(4);
myInts.Add(6);
myInts.Add(24);

我的目标是从列表中获取第一个未使用(可用)的值。

(集合中尚未存在的第一个正值)

在这种情况下，答案是 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 系列:Reimplementing LINQ to Objects: Part 17 - Except