Determinazione del primo valore disponibile in un elenco di numeri interi

Question

Ho ottenuto una semplice lista di interi.

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

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

Il mio obiettivo è quello di ottenere il primo valore non utilizzato (disponibile) dalla lista.

(il primo valore positivo che non è già presente nella collezione)

In questo caso, la risposta sarebbe 2.

Ecco il mio codice corrente:

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

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

C'è un modo migliore? Forse usando LINQ? come lo faresti?

Ovviamente qui ho usato gli ints per semplicità ma la mia domanda potrebbe applicarsi a qualsiasi tipo.

Answer 1

Che, fondamentalmente, vogliono che il primo elemento dalla sequenza 0..int.MaxValue che non è contenuta in myInts:

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

Modifica in risposta al commento:

Non c'è alcuna penalità prestazioni qui per iterare fino a int.MaxValue. Quello che Linq sta per internamente è creare un hashtable per myInts e quindi iniziare l'iterazione sulla sequenza creata da Enumerable.Range() - una volta che il primo elemento non contenuto nell'hashtable viene trovato che il numero intero è restituito dal metodo Except() e restituito da FirstOrDefault() - dopo di che l'iterazione si interrompe. Ciò significa che lo sforzo complessivo è O (n) per la creazione della tabella hash e quindi del caso peggiore O (n) per l'iterazione sulla sequenza in cui n è il numero di numeri interi in myInts.

Per ulteriori informazioni su Except() vedi serie EduLinq del cioè Jon Skeet: Reimplementing LINQ to Objects: Part 17 - Except

Answer 2

Beh, se la lista è ordinata dal più piccolo al più grande e contiene valori da 0 a infinito positivo, si può semplicemente accedere all'elemento i-esimo. if (myInts[i] != i) return i; che sarebbe essenzialmente lo stesso, ma non necessita di scorrere l'elenco per ogni controllo Contains (il metodo Contains scorre l'elenco, trasformando l'algoritmo in un O (n-quadrato) anziché in O (n)) .