确定整数列表中的第一个可用值 [英] Determining the first available value in a list of integers

问题描述

我有一个简单的int列表。

  List< int& myInts = new List< int>（）; 
 
 myInts.Add（0）; 
 myInts.Add（1）; 
 myInts.Add（4）; 
 myInts.Add（6）; 
 myInts.Add（24）; 
  

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

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

在这种情况下，答案为2。 p>

这是我当前的代码：

  int GetFirstFreeInt（）
 {
 for（int i = 0; i  {
 if（！myInts.Contains（i））
 return i; 
} 
 
 throw new InvalidOperationException（All integers are already used。）; 
} 
  

有更好的方法吗？也许使用LINQ？

当然，这里我使用int来简化，但我的问题可以应用于任何类型。

解决方案

您基本上需要 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 中的整数数。 
 
 
 
有关的更多信息，请参阅Jon Skeet的EduLinq系列：将LINQ重新实现为对象：第17部分 - 除了 
 
I got a simple List of ints.
List<int> myInts = new List<int>();

myInts.Add(0);
myInts.Add(1);
myInts.Add(4);
myInts.Add(6);
myInts.Add(24);
My goal is to get the first unused (available) value from the List.

(the first positive value that's not already present in the collection)

In this case, the answer would be 2.

Here's my current code :
int GetFirstFreeInt()
{
    for (int i = 0; i < int.MaxValue; ++i)
    {
        if(!myInts.Contains(i))
            return i;
    }

    throw new InvalidOperationException("All integers are already used.");
}
Is there a better way? Maybe using LINQ? How would you do this?

Of course here I used ints for simplicity but my question could apply to any type.
解决方案
You basically want the first element from the sequence 0..int.MaxValue that is not contained in myInts:
int? firstAvailable = Enumerable.Range(0, int.MaxValue)
                                .Except(myInts)
                                .FirstOrDefault();
Edit in response to comment:

There is no performance penalty here to iterate up to int.MaxValue. What Linq is going to to internally is create a hashtable for myInts and then begin iterating over the sequence created by Enumerable.Range() - once the first item not contained in the hashtable is found that integer is yielded by the Except() method and returned by FirstOrDefault() - after which the iteration stops. This means the overall effort is O(n) for creating the hashtable and then worst case O(n) for iterating over the sequence where n is the number of integers in myInts.

For more on Except() see i.e. Jon Skeet's EduLinq series: Reimplementing LINQ to Objects: Part 17 - Except

                        
这篇关于确定整数列表中的第一个可用值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！