Trovare un singolo numero in un elenco [duplicato]

Question

Questa domanda ha già una risposta qui:

• Come trovare l'unico numero in un array che non ricorre due volte [duplicato] 5 risposte

Quale sarebbe il miglior algoritmo per trovare un numero che ricorre solo una volta in un elenco in cui tutti gli altri numeri compaiono esattamente due volte?

Quindi, nell'elenco degli interi (prendiamolo come un array) ogni intero si ripete esattamente due volte, tranne uno.Per trovarlo, qual è l'algoritmo migliore.

Answer 1

Il modo più veloce (O(n)) e più efficiente in termini di memoria (O(1)) è con l'operazione XOR.

In C:

int arr[] = {3, 2, 5, 2, 1, 5, 3};

int num = 0, i;

for (i=0; i < 7; i++)
    num ^= arr[i];

printf("%i\n", num);

Questo stampa "1", che è l'unico che si verifica una volta.

Funziona perché la prima volta che premi un numero contrassegna la variabile num con se stessa e la seconda volta rimuove num con se stessa (più o meno).L'unico che rimane non contrassegnato è il tuo non duplicato.

Answer 2

A proposito, puoi espandere questa idea per trovarla molto rapidamente due numeri univoci in un elenco di duplicati.

Chiamiamo i numeri univoci a e b.Per prima cosa prendi lo XOR di tutto, come suggerito da Kyle.Ciò che otteniamo è a^b.Conosciamo a^b != 0, poiché a != b.Scegli 1 bit qualsiasi di a^b e usalo come maschera, più in dettaglio:scegli x come potenza di 2 in modo che x & (a^b) sia diverso da zero.

Ora dividi l'elenco in due sottoliste: una sottolista contiene tutti i numeri y con y&x == 0 e il resto va nell'altra sottolista.A proposito, abbiamo scelto x, sappiamo che a e b si trovano in contenitori diversi.Sappiamo anche che ogni coppia di duplicati è ancora nello stesso secchio.Quindi ora possiamo applicare il vecchio trucco "XOR-em-all" a ciascun bucket in modo indipendente e scoprire cosa sono a e b completamente.

Bam.

Answer 3

O(N) tempo, O(N) memoria

HT= tabella hash

Ht.clear () supera l'elenco per ogni elemento che vedi

if(HT.Contains(item)) -> HT.Remove(item)
else
ht.add(item)

alla fine, l'articolo nell'HT è l'articolo che stai cercando.

Nota (credito @Jared Updike):Questo sistema troverà tutte le istanze dispari di elementi.

---

commento:Non vedo come le persone possano votare a favore delle soluzioni che ti offrono prestazioni NLogN.in quale universo è "meglio"?Sono ancora più scioccato che tu abbia contrassegnato la soluzione NLogN della risposta accettata ...

Sono d'accordo, tuttavia, sul fatto che se la memoria deve essere costante, allora NLogN sarebbe (finora) la soluzione migliore.

Answer 4

La soluzione di Kyle ovviamente non rileverebbe le situazioni in cui il set di dati non segue le regole.Se tutti i numeri fossero in coppia, l'algoritmo darebbe come risultato zero, esattamente lo stesso valore che se zero fosse l'unico valore con un'unica occorrenza.

Se ci fossero più valori di occorrenze singole o triple, anche il risultato sarebbe un errore.

Testare il set di dati potrebbe finire con un algoritmo più costoso, sia in termini di memoria che di tempo.

La soluzione di Csmba mostra alcuni dati di errore (nessuno o più di un singolo valore di occorrenza), ma non altri (quadruple).Per quanto riguarda la sua soluzione, a seconda dell'implementazione di HT, la memoria e/o il tempo sono maggiori di O(n).

Se non possiamo essere sicuri della correttezza del set di input, sarebbe fattibile ordinare e contare o utilizzare una tabella hash che conta le occorrenze con l'intero stesso come chiave hash.

Answer 5

Direi che utilizzare un algoritmo di ordinamento e poi scorrere l'elenco ordinato per trovare il numero è un buon modo per farlo.

E ora il problema è trovare il "miglior" algoritmo di ordinamento.Esistono molti algoritmi di ordinamento, ognuno con i suoi punti forti e deboli, quindi questa è una domanda piuttosto complicata.IL Voce di Wikipedia sembra una bella fonte di informazioni a riguardo.

Answer 6

Implementazione in Ruby:

a = [1,2,3,4,123,1,2,.........]
t = a.length-1
for i in 0..t
   s = a.index(a[i])+1
   b = a[s..t]
   w = b.include?a[i]
   if w == false
       puts a[i]
   end
end

Answer 7

Devi specificare cosa intendi per "migliore" - per alcuni, la velocità è tutto ciò che conta e qualificherebbe una risposta come "migliore" - per altri, potrebbero perdonare qualche centinaio di millisecondi se la soluzione fosse più leggibile.

Il "migliore" è soggettivo a meno che tu non sia più specifico.

---

Detto ciò:

Scorri i numeri, per ogni numero cerca quel numero nell'elenco e quando raggiungi il numero che restituisce solo 1 per il numero di risultati della ricerca, hai finito.

Answer 8

Sembra che la cosa migliore che potresti fare sia scorrere l'elenco, per ogni elemento aggiungerlo a un elenco di elementi "visti" oppure rimuoverlo da "visto" se è già lì, e alla fine il tuo elenco di "visti" " gli elementi includeranno l'elemento singolare.Questo è O(n) rispetto al tempo e n rispetto allo spazio (nel peggiore dei casi, sarebbe molto meglio se l'elenco fosse ordinato).

Il fatto che siano numeri interi non influisce davvero, dal momento che non c'è niente di speciale che puoi fare sommandoli...è lì?

Domanda

Non capisco perché la risposta selezionata sia "migliore" secondo qualsiasi standard.O(N*lgN) > O(N), e modifica la lista (oppure ne crea una copia, cosa comunque più dispendiosa in spazio e tempo).Mi sto perdendo qualcosa?

Answer 9

Dipende da quanto grandi/piccoli/diversi sono i numeri.Potrebbe essere applicabile un ordinamento digitale che ridurrebbe notevolmente il tempo di ordinamento della soluzione O (N log N).

Answer 10

Il metodo di ordinamento e il metodo XOR hanno la stessa complessità temporale.Il metodo XOR è O(n) solo se si presuppone che lo XOR bit per bit di due stringhe sia un'operazione a tempo costante.Ciò equivale a dire che la dimensione degli interi nell'array è delimitata da una costante.In tal caso puoi utilizzare Radix sort per ordinare l'array in O(n).

Se i numeri non sono limitati, lo XOR bit per bit impiega il tempo O(k) dove k è la lunghezza della stringa di bit e il metodo XOR impiega O(nk).Ora ancora una volta Radix sort ordinerà l'array nel tempo O (nk).

Answer 11

Potresti semplicemente mettere gli elementi del set in un hash finché non trovi una collisione.In Ruby, questa è una battuta.

def find_dupe(array)
  h={}
  array.detect { |e| h[e]||(h[e]=true; false) }
end

COSÌ, find_dupe([1,2,3,4,5,1]) restituirebbe 1.

Questa è in realtà una domanda "trucco" comune nelle interviste.Normalmente si tratta di un elenco di numeri interi consecutivi con un duplicato.In questo caso l'intervistatore spesso chiede che tu utilizzi la somma gaussiana di N-trucco con numeri interi, ad es. n*(n+1)/2 sottratto dalla somma effettiva.La risposta da manuale è qualcosa del genere.

def find_dupe_for_consecutive_integers(array)
  n=array.size-1   # subtract one from array.size because of the dupe
  array.sum - n*(n+1)/2
end