Determinación del primer valor disponible en una lista de enteros

Obtuve una lista simple de ints.Determinación del primer valor disponible en una lista de enteros

List<int> myInts = new List<int>(); 

myInts.Add(0); 
myInts.Add(1); 
myInts.Add(4); 
myInts.Add(6); 
myInts.Add(24);

Mi objetivo es obtener el primer valor no utilizado (disponible) de la lista.

(el primer valor positivo que no está ya presente en la colección)

En este caso, la respuesta sería 2.

Aquí está mi código actual:

int GetFirstFreeInt() 
{ 
    for (int i = 0; i < int.MaxValue; ++i) 
    { 
     if(!myInts.Contains(i)) 
      return i; 
    } 

    throw new InvalidOperationException("All integers are already used."); 
}

¿Existe una ¿mejor manera? Tal vez usando LINQ? ¿Cómo harías esto?

Por supuesto, aquí utilicé ints para simplificar, pero mi pregunta podría aplicarse a cualquier tipo.

Fuente

2012-01-14 asmo

¿La lista está ordenada por orden ascendente? –

@OsmanTuran Nope. No se garantiza que la lista esté ordenada de ninguna manera. Lo siento, olvidé mencionar eso. – asmo

Es, básicamente, quieren que el primer elemento de la secuencia 0..int.MaxValue que no está contenida en myInts:

int? firstAvailable = Enumerable.Range(0, int.MaxValue) 
           .Except(myInts) 
           .FirstOrDefault();

Editar en respuesta al comentario:

Hay ninguna pena actuación aquí para iterar hasta int.MaxValue. Lo que Linq va a hacer internamente es crear una tabla hash para myInts y luego comenzar a iterar sobre la secuencia creada por Enumerable.Range() - una vez que el primer elemento no contenido en la tabla hash se encuentra que el entero es cedido por el método Except() y devuelto por FirstOrDefault() - luego la iteración se detiene. Esto significa que el esfuerzo general es O (n) para crear el hashtable y luego el peor caso O (n) para iterar sobre la secuencia donde n es el número de enteros en myInts.

Para más información sobre Except() ver series EduLinq de decir Jon Skeet: Reimplementing LINQ to Objects: Part 17 - Except

Fuente

2012-01-14 22:18:39 BrokenGlass

Bien, pero ¿y si myInts contiene {0,1,2,3}? Necesitaría el método para devolver 4 en ese caso. – asmo

@asmo: Ah, eso no estaba claro en la pregunta: en ese caso, use int.MaxValue como límite superior no 'myInts.Max()' - Actualizaré la respuesta. – BrokenGlass

@asmo Hacerlo 'myInts.Max() + 1' –

Bueno, si la lista se ordena de menor a mayor y contiene valores de 0 a infinito positivo, simplemente podría acceder al elemento i-ésimo. if (myInts[i] != i) return i; que sería esencialmente el mismo, pero no es necesario iterar a través de la lista para cada Contains comprobación (el método Contiene itera a través de la lista, convirtiendo su algoritmo en O (n-cuadrado) en lugar de O (n)) .

Fuente

2012-01-14 22:19:21 GGulati

+1.Sí, y si la lista no está ordenada, es más rápido ordenarla antes de hacer la prueba de GGulati. La ordenación es O (n * log (n)), que es más rápido que O (n^2) para la verificación Contiene iterada. (Si estoy en lo correcto, Microsoft está utilizando QuickSort). –

La ordenación no será más rápida que el uso de un HashSet que es O (n) para el problema de OP. – BrokenGlass

Determinación del primer valor disponible en una lista de enteros

Respuesta

Cuestiones relacionadas