Verificar si falta el número en la secuencia

Question

Tengo un List<int> que contiene 1,2,4,7,9 por ejemplo.

que tienen un rango de 0 a 10.

¿Hay una manera de determinar qué números faltan en esa secuencia?

pensé LINQ podría proporcionar una opción, pero no puedo ver uno

En el mundo real mi lista podría contener 100.000 artículos lo que el rendimiento es clave

Answer 1

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

Answer 2

Girar el rango que desea comprobar en un HashSet:

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

devolverá los valores que no están en values.

Answer 3

El método Except de LINQ sería el más legible. Si se realiza de manera adecuada para usted o no, será una cuestión de prueba.

E.g.

range.Except(listOfValues); 

Edición

Aquí está el programa que utilicé para mi mini-referencia, para otros para tapar lejos con:

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

Crear una matriz de elementos num

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"); 
} 

Answer 5

 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 6

Si el rango es predecible que sugieren la siguiente solución:

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(); 
} 

Saludos, y00daa

Answer 7

Esto no utiliza LINQ pero funciona en tiempo lineal.

Supongo que la lista de entrada está ordenada.

Esto toma 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; 
    } 
} 

---

Esto debe tomar O(n), donde n es la longitud del intervalo total.

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 8

Bien, en realidad, cree una nueva lista que sea paralela a la lista inicial y ejecute el método Excepto sobre ella ...

He creado una totalmente LINQ respuesta utilizando el método Aggregate lugar para encontrar las missings:

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;  
}); 

La lista de desaparecidos tiene esto después de que el código anterior se ha ejecutado:

3, 5, 6, 8 

Answer 9

Un método alternativo que funciona en general para cualquier dos IEnunumerable<T> donde T :IComparable. Si los IEnumerables están ordenados, esto funciona en O (1) memoria (es decir, no hay otra creación de ICollection y sustrayendo, etc.) y en O (n) tiempo.

El uso de IEnumerable<IComparable> y GetEnumerator hace que este sea un poco menos legible, pero mucho más general.

Implementación

/// <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(); 
     } 
    } 
} 

Uso

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