按顺序检查丢失的数字

我有一个List<int> ，其中包含1,2,4,7,9例如。

我有一个从0到10的范围。

有没有办法确定在这个序列中缺less的数字？

我认为LINQ可能提供一个选项，但我看不到一个

在现实世界中，我的列表可能包含100,000个项目，所以性能是关键

Answer 1

 var list = new List<int>(new[] { 1, 2, 4, 7, 9 }); var result = Enumerable.Range(0, 10).Except(list); 

Answer 2

把你想要检查的范围变成一个HashSet：

 public IEnumerable<int> FindMissing(IEnumerable<int> values) { HashSet<int> myRange = new HashSet<int>(Enumerable.Range(0,10)); myRange.ExceptWith(values); return myRange; } 

将返回不在values中的values 。

Answer 3

LINQ的Except方法将是最可读的。 它是否适合你的工作将是一个testing的问题。

例如

 range.Except(listOfValues); 

编辑

以下是我用于迷你基准testing的程序，其他人可以使用它：

 static void Main() { var a = Enumerable.Range(0, 1000000); var b = new List<int>(); for (int i = 0; i < 1000000; i += 10) { b.Add(i); } Stopwatch sw = new Stopwatch(); sw.Start(); var c = a.Except(b).ToList(); sw.Stop(); Console.WriteLine("Milliseconds {0}", sw.ElapsedMilliseconds ); sw.Reset(); Console.ReadLine(); } 

Answer 4

  List<int> selectedNumbers = new List<int>(){8, 5, 3, 12, 2}; int firstNumber = selectedNumbers.OrderBy(i => i).First(); int lastNumber = selectedNumbers.OrderBy(i => i).Last(); List<int> allNumbers = Enumerable.Range(firstNumber, lastNumber - firstNumber + 1).ToList(); List<int> missingNumbers = allNumbers.Except(selectedNumbers).ToList(); foreach (int i in missingNumbers) { Response.Write(i); } 

Answer 5

如果范围是可预测的，我build议以下解决scheme：

 public static void Main() { //set up the expected range var expectedRange = Enumerable.Range(0, 10); //set up the current list var currentList = new List<int> {1, 2, 4, 7, 9}; //get the missing items var missingItems = expectedRange.Except(currentList); //print the missing items foreach (int missingItem in missingItems) { Console.WriteLine(missingItem); } Console.ReadLine(); } 

问候，y00daa

Answer 6

这不使用LINQ，但它在线性时间。

我假设input列表是sorting的。

这需要O(list.Count) 。

 private static IEnumerable<int> get_miss(List<int> list,int length) { var miss = new List<int>(); int i =0; for ( i = 0; i < list.Count - 1; i++) { foreach (var item in Enumerable.Range(list[i] + 1, list[i + 1] - list[i] - 1)) { yield return item; } } foreach (var item in Enumerable.Range(list[i]+1,length-list[i])) { yield return item; } } 

---

这应该采取O(n) ，其中n是全范围的长度。

  static void Main() { List<int> identifiers = new List<int>() { 1, 2, 4, 7, 9 }; Stopwatch sw = new Stopwatch(); sw.Start(); List<int> miss = GetMiss(identifiers,150000); sw.Stop(); Console.WriteLine("{0}",sw.ElapsedMilliseconds); } private static List<int> GetMiss(List<int> identifiers,int length) { List<int> miss = new List<int>(); int j = 0; for (int i = 0; i < length; i++) { if (i < identifiers[j]) miss.Add(i); else if (i == identifiers[j]) j++; if (j == identifiers.Count) { miss.AddRange(Enumerable.Range(i + 1, length - i)); break; } } return miss; } 

Answer 7

一个替代方法，一般适用于任何两个IEnunumerable<T> ，其中T : IComparable 。 如果IEnumerables都是sorting的，这工作在O（1）内存 （即没有创build另一个ICollection和减去等），并在O（n）时间 。

IEnumerable<IComparable>和GetEnumerator使得这个可读性稍差，但更一般。

履行

 /// <summary> /// <para>For two sorted IEnumerable&lt;T&gt; (superset and subset),</para> /// <para>returns the values in superset which are not in subset.</para> /// </summary> public static IEnumerable<T> CompareSortedEnumerables<T>(IEnumerable<T> superset, IEnumerable<T> subset) where T : IComparable { IEnumerator<T> supersetEnumerator = superset.GetEnumerator(); IEnumerator<T> subsetEnumerator = subset.GetEnumerator(); bool itemsRemainingInSubset = subsetEnumerator.MoveNext(); // handle the case when the first item in subset is less than the first item in superset T firstInSuperset = superset.First(); while ( itemsRemainingInSubset && supersetEnumerator.Current.CompareTo(subsetEnumerator.Current) >= 0 ) itemsRemainingInSubset = subsetEnumerator.MoveNext(); while ( supersetEnumerator.MoveNext() ) { int comparison = supersetEnumerator.Current.CompareTo(subsetEnumerator.Current); if ( !itemsRemainingInSubset || comparison < 0 ) { yield return supersetEnumerator.Current; } else if ( comparison >= 0 ) { while ( itemsRemainingInSubset && supersetEnumerator.Current.CompareTo(subsetEnumerator.Current) >= 0 ) itemsRemainingInSubset = subsetEnumerator.MoveNext(); } } } 

用法

 var values = Enumerable.Range(0, 11); var list = new List<int> { 1, 2, 4, 7, 9 }; var notIncluded = CompareSortedEnumerables(values, list); 

Answer 8

好吧，真的，创build一个新的列表，并列初始列表，并运行该方法除了它…

我已经使用Aggregate方法创build了完整的linq答案，而不是find错误：

 var list = new List<int>(new[] { 1, 2, 4, 7, 9 }); // Assumes list is ordered at this point list.Insert(0, 0); // No error checking, just put in the lowest and highest possibles. list.Add(10); // For real world processing, put in check and if not represented then add it/them. var missing = new List<int>(); // Hold any missing values found. list.Aggregate ((seed, aggr) => // Seed is the previous #, aggr is the current number. { var diff = (aggr - seed) -1; // A difference between them indicates missing. if (diff > 0) // Missing found...put in the missing range. missing.AddRange(Enumerable.Range((aggr - diff), diff)); return aggr; }); 

上面的代码执行后，缺less的列表有这个：

 3, 5, 6, 8 

Answer 9

创build一个数组项目

 const int numItems = 1000; bool found[numItems] = new bool[numItems]; List<int> list; PopulateList(list); list.ForEach( i => found[i] = true ); // now iterate found for the numbers found for(int count = 0; i < numItems; ++numItems){ Console.WriteList("Item {0} is {1}", count, found[count] ? "there" : "not there"); }