Qual è il modo ottimale per calcolare quale numero intero in una lista manca?

Question

Recentemente, in un'intervista, mi hanno fatto domande tecniche. Uno era come dovresti calcolare quale numero in una lista di lunghezza n-1 mancava. L'elenco conteneva tutti i numeri da 1 an, tranne i dove 1 < = i < = n. I numeri non erano in ordine. La mia soluzione era di aggiungerli tutti, quindi sottrarre quella dal calcolo dei numeri da 1 a n, aggiungendo 1 a n e moltiplicando per n/2 o (n-1)/2 come appropriato. Ma ho avuto la sensazione che esistesse un modo migliore per farlo. Qual è la soluzione ottimale?

Answer 1

La tua risposta è abbastanza buona, secondo me.

Ma alcune persone - forse il tuo intervistatore è uno di loro - sono preoccupate per l'eccedenza e così via. In tal caso, utilizzare XOR anziché l'aggiunta.

Per ottenere lo XOR degli interi da 0 a n, basta XOR insieme gli indici di matrice durante il ciclo. Dato lo XOR degli interi da 0 a n, e lo XOR degli elementi dell'array, basta XOR i due di questi insieme per ottenere l'elemento mancante.

P.S. La somma dei numeri interi da 1 a n è sempre (n + 1) * n/2

Answer 2

mentre si scorre l'array per calcolare la somma, è possibile verificare se un numero si sta ripetendo.

Answer 3

Il tuo metodo è assolutamente valido. È ottimale in termini di spazio e tempo. L'overflow può essere l'unico problema con esso.

Un altro metodo possibile potrebbe essere l'utilizzo di un hashSet. Creare un hash iniziale con valori 1-> N. Ora per ogni numero che incontri nella lista - cancella quel valore dal hashSet. Alla fine, il valore che rimane nell'hashSet è il valore mancante.

Questo metodo è O (N) nella complessità di tempo e spazio. Il tuo metodo (con esclusione del limite) era O (N) nel tempo e complessità O (1). Il fattore "n" aggiunto per lo spazio è il costo per eliminare l'overflow.

Answer 4

La soluzione è più o meno ottimale con una modifica, come sottolinea @Nemo la somma di numeri interi da 1 a n è sempre (n+1) * n/2

Vale anche la pena sottolineare che il vostro approccio è multi-thread in grado (e potrebbe adatto per valori molto grandi di N), dividere l'array in parti, quindi ottenere la somma di ogni parte di matrice in un thread, quindi aggiungere le somme di parti. Dipende da quale sovraccarico di threading viene confrontato con l'aggiunta di numeri in un array.

Se siete preoccupati per overflow, e i valori sono sempre Int32 (come la maggior parte dei valori .Length sono compresi gli array) poi basta memorizzare la somma come un Int64, la somma di tutti i valori intero positivo (((long)int.MaxValue) +1L) * (int.MaxValue/2) = 2305843007066210304 che è ancora in grado di adattarsi all'interno di un int64 con un .MaxValue = 9223372036854775807.

L'altra risposta come menzionata da altri è quella di XOR ogni elemento e mantenere un XOR in esecuzione, ma poi è necessario elaborare una formula per ottenere lo XOR totale previsto nel tempo O(1).

Molto probabilmente l'intervistatore sta cercando di vedere se ti rendi conto c'è una soluzione O(N) con O(1) di memoria (che la vostra risposta è), piuttosto che l'ordinamento della matrice e di essere molto più lento per grandi valori di N.

Per migliorare ulteriormente la soluzione nel codice, sarebbe opportuno utilizzare un puntatore per accedere alla matrice anziché al valore dell'indice (che se il codice è C# sarà un miglioramento ragionevole).