Vérifier le numéro manquant dans l’ordre

J’ai une List qui contient 1,2,4,7,9 par exemple.

J’ai une plage de 0 à 10.

Y a-t-il un moyen de déterminer quels nombres manquent dans cette séquence?

Je pensais que LINQ pourrait fournir une option mais je ne peux pas en voir une

Dans le monde réel, ma liste pourrait contenir 100 000 éléments, la performance est donc essentielle

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

Tournez la plage que vous souhaitez vérifier dans un HashSet:

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

Renvoie les valeurs qui ne sont pas dans les values .

La méthode LINQ’s Except serait la plus lisible. Que cela fonctionne ou non pour vous serait une question de test.

Par exemple

 range.Except(listOfValues); 

modifier

Voici le programme que j’ai utilisé pour mon mini-benchmark, pour que d’autres puissent le twigr avec:

 static void Main() { var a = Enumerable.Range(0, 1000000); var b = new List(); 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(); } 

Cette méthode n’utilise pas LINQ et fonctionne en général pour deux IEnunumerable where T :IComparable

 public static IEnumerable FindMissing(IEnumerable superset, IEnumerable subset) where T : IComparable { bool include = true; foreach (var i in superset) { foreach (var j in subset) { include = i.CompareTo(j) == 0; if (include) break; } if (!include) yield return i; } } 
  List selectedNumbers = new List(){8, 5, 3, 12, 2}; int firstNumber = selectedNumbers.OrderBy(i => i).First(); int lastNumber = selectedNumbers.OrderBy(i => i).Last(); List allNumbers = Enumerable.Range(firstNumber, lastNumber - firstNumber + 1).ToList(); List missingNumbers = allNumbers.Except(selectedNumbers).ToList(); foreach (int i in missingNumbers) { Response.Write(i); } 

Si la plage est prévisible, je suggère la solution suivante:

 public static void Main() { //set up the expected range var expectedRange = Enumerable.Range(0, 10); //set up the current list var currentList = new List {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(); } 

Cordialement, y00daa

Une méthode alternative qui fonctionne en général pour deux IEnunumerableT : IComparable . Si les IEnumerables sont tous deux sortingés, cela fonctionne dans la mémoire O (1) (c.-à-d. Qu’il n’y a pas de création d’une autre collection et de soustraction, etc.) et dans O (n) .

L’utilisation de IEnumerable et de GetEnumerator rend cela un peu moins lisible, mais beaucoup plus général.

la mise en oeuvre

 ///  /// For two sorted IEnumerable<T> (superset and subset), /// returns the values in superset which are not in subset. ///  public static IEnumerable CompareSortedEnumerables(IEnumerable superset, IEnumerable subset) where T : IComparable { IEnumerator supersetEnumerator = superset.GetEnumerator(); IEnumerator 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(); } } } 

Usage

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

Cela n’utilise pas LINQ mais cela fonctionne en temps linéaire.

Je suppose que cette liste d’entrées est sortingée.

Cela prend O(list.Count) .

 private static IEnumerable get_miss(List list,int length) { var miss = new List(); 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; } } 

Cela devrait prendre O(n) où n est la longueur de la plage complète.

  static void Main() { List identifiers = new List() { 1, 2, 4, 7, 9 }; Stopwatch sw = new Stopwatch(); sw.Start(); List miss = GetMiss(identifiers,150000); sw.Stop(); Console.WriteLine("{0}",sw.ElapsedMilliseconds); } private static List GetMiss(List identifiers,int length) { List miss = new List(); 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; } 

Ok, vraiment, crée une nouvelle liste qui soit parallèle à la liste initiale et exécute la méthode, sauf par dessus …

J’ai créé une réponse entièrement linq en utilisant la méthode Aggregate au lieu de trouver les échecs:

 var list = new List(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(); // 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; }); 

La liste manquante a ceci après que le code ci-dessus a été exécuté:

 3, 5, 6, 8 

Créer un tableau d’éléments num

 const int numItems = 1000; bool found[numItems] = new bool[numItems]; List 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"); }