Trova i duplicati in un array in tempo O (N)

Question

C'è un modo per trovare tutti gli elementi duplicati in un array di elementi N in tempo O (N)?

Esempio:

ingresso: 11, 29, 81, 14, 43, 43, 81, 29

uscita: 29, 81, 43

ordinamento dell'input e facendo una scansione lineare per rilevare i duplicati distrugge l'ordine e dà l'output: 29,43,81.

Ordinando-by-chiave altro array di indici {0,1,...N-1} secondo l'array dato per ottenere {1,4,2} e quindi classificare l'insieme risultante di indici per ottenere {1,2,4} ci darà {29,81,43}, ma questo richiede O(N logN) tempo.

Esiste un algoritmo O (N) per risolvere questo problema?

P.S. Ho dimenticato di aggiungere: non voglio usare tabelle hash. Sto cercando una soluzione non hash.

Answer 1

Credo che una buona soluzione (utilizzo di memoria decente, può essere utilizzata per determinare immediatamente se una voce è già stata vista in modo da preservare l'ordine e con una complessità lineare) è a trie.

Se si inserisce gli elementi nel trie come se fossero una stringa con ogni cifra (partendo dalla MSD) in ciascun nodo, è possibile staccare questo con una complessità di O (m N) dove m è la lunghezza media dei numeri nelle cifre in base 10.

È sufficiente scorrere su tutte le voci e inserirle nel trie. Ogni volta che un elemento esiste già, lo salti e passa al successivo. I duplicati in questo (a differenza della mia precedente risposta di un ordinamento digitale) si troveranno immediatamente anziché nell'ultima iterazione o cosa no.

Non sono sicuro di trarre vantaggio dall'utilizzo di un albero di suffisso qui, poiché la "base" dei caratteri immessi nel trie è solo 10 (rispetto alla base 128 per le stringhe ANSI), ma è possibile.

Answer 2

Se gli input sono tutti interi piccoli, è possibile utilizzare uno counting sort che viene eseguito in tempo O (n) e richiede uno spazio O (m) dove m è la dimensione dell'intervallo di possibili input.

Come ottimizzazione dello spazio è sufficiente utilizzare un array di bit e utilizzare un singolo bit (anziché un conteggio) per memorizzare se si è visto quell'elemento prima o no.

Answer 3

Se si conosce il valore massimo che si può fare in questo modo,
dispone di un array separato con la lunghezza del valore massimo

int[max] secondarray; 

    for(int i=o;i<arrayFirst.length;i++){ 
     if(secondarray[arrayFirst[i]]==0){ 
      secondarray[arrayFirst[i]]==arrayFirst[i]; 
     }else{ 
      result.add(arrayFirst[i]); 
      } 
    } 

Answer 4

Trovare i duplicati è altrettanto difficile come l'ordinamento. La soluzione migliore è sfruttare alcune proprietà del tuo input per ottenere un ordinamento O (N).

Answer 5

Sembra che tu sia sfavorevole all'allocazione di qualsiasi spazio aggiuntivo. Tuttavia, una tabella hash è ancora la soluzione giusta per la velocità. Onestamente, la maggior parte delle implementazioni di hash table per dati semplici come gli interi sono così sovrappesate dalla loro unica soluzione che va bene per me, a seconda di cosa ho bisogno. Può trasformare codice lento in codice veloce quando ne hai bisogno per un lavoro relativamente piccolo.

Inoltre, se la vostra obiezione alle tabelle è che distruggono per poi forse si consiglia di utilizzare loro un po 'diverso per ottenere O atteso (n) di mantenere l'ordine:

Creare una tabella di hash che mappa la tua elementi di array a due bit come campo di conteggio da zero a tre e trenta bit come indice nell'array di elementi. A meno che non abbiate oltre un miliardo di valori nel vostro array, trenta bit sono sufficienti. In questo modo i tuoi valori hash sono solo una singola parola a 32 bit.

Passare attraverso gli elementi nella matrice. Se un elemento non è nella tabella, inserire il valore nella tabella hash e impostare il campo count su zero. Non importa quale sia la porzione dell'indice quando la si archivia. Se l'elemento si trova nella tabella e il campo count è zero, esegui il push su 1 e memorizza l'indice dell'elemento con il nuovo valore del campo count. Se il campo count è già uno o più, impostalo su due e non toccare l'indice memorizzato - lascialo come è.

Passare nuovamente tra gli elementi dell'array.Cerca ogni elemento e se il suo indice è quello memorizzato e il campo conteggio associato è maggiore di zero, stampalo.

Questo dovrebbe fornire ciò che si desidera nell'ordine corretto con O (n) ora. Ma usa tabelle hash che non sono desiderate per un motivo sconosciuto. Consiglio vivamente di accettare una soluzione come questa o di spiegare i limiti in modo da ottenere una soluzione più mirata.

Answer 6

È possibile eseguire questa operazione in O (n), ma ciò richiederebbe che l'array fosse integer. Lo spazio richiesto per questo può essere però della dimensione dell'ordine da -2^32 a 2^32. Quello che dovresti fare è trovare il massimo e il minimo dell'array originale (arrayorig). Quindi crea due array (arraynew +) e (arraynew-).

La dimensione di (arraynew +) sarà max (arraorig) -min (arrayorig) se tutti i valori in arrayorig sono +, altrimenti la dimensione di (arraynew +) sarà max (arrayorig).

La dimensione (arraynew-) sarà zero se tutti i valori sono positivi, altrimenti saranno uguali al valore assoluto di min (arrayorig).

Quindi è possibile scorrere l'arrayorig e incrementare il valore di 1 di (arraynew-) o (arraynew +) nell'indice corrispondente al valore di arraorig, se il valore è positivo, l'incremento deve essere eseguito su (arraynew +) altro se il suo incremento negativo dovrebbe essere fatto a (arraynew-) all'indice di (arraynew-) che è uguale al valore assoluto di arrayorig. Allora tutti gli indici di (arraynew +) e ((arraynew-) con valore> 1 sono i valori distinti di arrayorig.

Answer 7

void printRepeating(int arr[], int size) 
{ 
int i; 
    printf("The repeating elements are: \n"); 
for (i = 0; i < size; i++) 
{ 
if (arr[abs(arr[i])] >= 0) 
    arr[abs(arr[i])] = -arr[abs(arr[i])]; 
else 
    printf(" %d ", abs(arr[i])); 
} 
    }