c# - 在 List 中找到第一个可用的 long

Question

好的，这应该很有趣。

假设我有以下代码:

在这个例子中，第一个可用的数字是 2 .

List<long> myList = new List<long>(){0,1,10,3};

在这个例子中，第一个可用的数字是“4”。

List<long> myList = new List<long>(){0,1,2,3};

有什么想法吗？

Answer 1

所以“可用”是指“列表中不存在的最小非负数”？

我很想写这样的东西:

HashSet<long> existing = new HashSet<long>(list);
for (long x = 0; x < long.MaxValue; x++)
{
    if (!existing.Contains(x))
    {
        return x;
    }
}
throw new InvalidOperationException("Somehow the list is enormous...");

编辑:或者，您可以对列表进行排序，然后找到索引与值不同的第一个值...

var ordered = list.OrderBy(x => x);
var differences = ordered.Select((value, index) => new { value, index })
                         .Where(pair => pair.value != pair.index)
                         .Select(pair => (int?) pair.index);
var firstDifference = differences.FirstOrDefault();
long nextAvailable = firstDifference ?? list.Count;

最后一行是处理列表从 0 开始连续的情况。另一种选择是:

var nextAvailable = list.Concat(new[] { long.MaxValue })
                        .OrderBy(x => x)
                        .Select((value, index) => new { value, index })
                        .Where(pair => pair.value != pair.index)
                        .Select(pair => pair.index)
                        .First();

只要列表不包含 long.MaxValue + 1 元素就没问题，当前版本的 .NET 中不包含这些元素。 (那是很多内存......)老实说，由于 Select 部分采用 元素，这已经超出了 int.MaxValue 元素>int 索引...