Trova i duplicati in un array

Dato un array di n elementi interi, scoprirai se ci sono duplicati nell’array nel tempo O (n) senza utilizzare spazi aggiuntivi.

Con spazio extra significa spazio extra di ordine O (n).

L’operatore Xor aiuta in alcun modo.

Se non ci sono informazioni aggiuntive, questa domanda sembra essere irrisolvibile, poiché questo è il Problema Distinzione Elemento , che è irrisolvibile con le restrizioni che hai fornito, nel tempo richiesto.

puoi consentire:

(1) più memoria e utilizzare un hashtable / hashset e soddisfare i criteri di tempo O (n). [iterare la matrice, controllare se un elemento è nella tabella hash, se si ha il dupes, altrimenti – inserire l’elemento nella tabella e continuare].

(2) più tempo , ordina l’array [O (nlogn)] e soddisfa i criteri dello spazio sub-lineare. [Dopo l’ordinamento, scorrere l’array e per ogni a[i] , a[i+1] , controllare se sono identici. Se non hai trovato una coppia identica, non hai duplicati]

EDIT : la dimostrazione di questa affermazione è un po ‘lunga e necessita di notazione matematica che non è supportata qui (sidenote: abbiamo davvero bisogno del supporto tex), ma l’idea è se modelliamo il nostro problema come un albero di calcolo algebrico (che è una fiera presupposto quando non è consentito l’hashing e spazio costante a disposizione), quindi, Ben o dimostrato nel suo articolo Lower Bounds For Algebraic Computation Trees (1983) (pubblicato in ACM Omega(nlogn) , tale distinzione elemento è il problema Omega(nlogn) sotto questo modello. Lubiw ha mostrato che la stessa conclusione si applica anche quando ci si limita ai numeri interi nel 1991: Un limite inferiore per il problema di distinzione degli elementi interi , ma questi articoli concludono che sotto il modello di calcolo algebrico – Problema Distinzione di intero è Omega (nlogn) .

Ordinamento diretto sul posto seguito da scansione lineare

Algoritmo di ordinamento digitale radix

A seconda di ciò che effettivamente consideri la complessità temporale di un ordinamento Radix, questa soluzione è O (N), anche se la mia opinione personale non è così. Penso che se non si assuma l’ipotesi di tempo lineare per l’intero, allora il problema è irrisolvibile.

A causa del fatto che l’ordinamento è sul posto, è necessaria solo O (1) spazio di archiviazione aggiuntivo.

Il codice è tutto in C ++ 11

Step 1: Radix Sort in place

 template::value>::type* = nullptr> void RecurseOnRadixSort(std::vector& myArray, T mask, int zerosEnd, int onesBegin) { if (zerosEnd+1 >= onesBegin-1 || mask == 0) return; int zerosEnd2 = zerosEnd; int onesBegin2 = onesBegin; while(zerosEnd2+1 <= onesBegin2-1) { // swap ones to the right if ((myArray[zerosEnd2+1] & mask) != 0) { std::swap(myArray[zerosEnd2+1], myArray[onesBegin2-1]); --onesBegin2; } else ++zerosEnd2; } mask >>= 1; //recurse on lhs RecurseOnRadixSort(myArray, mask, zerosEnd, zerosEnd2+1); //recurse on rhs RecurseOnRadixSort(myArray, mask, onesBegin2-1, onesBegin); } template ::value>::type* = nullptr> void InPlaceRadixSort(std::vector& myArray) { int zerosEnd = -1; int onesBegin = static_cast(myArray.size()); T mask = static_cast(1) << sizeof(T)*8-1; while(zerosEnd+1 <= onesBegin-1) { if ( (myArray[zerosEnd+1] & mask) != 0) { std::swap(myArray[zerosEnd+1], myArray[onesBegin-1]); --onesBegin; } else ++zerosEnd; } mask = static_cast(1) << sizeof(T)*8-2; // need to reassign in case of signed datatype //recurse on lhs RecurseOnRadixSort(myArray, mask, -1, zerosEnd+1); //recurse on rhs RecurseOnRadixSort(myArray, mask, onesBegin-1, static_cast(myArray.size())); // swap negatives to the front auto iterSmallest = std::min_element(myArray.begin(), myArray.end()); if (*iterSmallest < 0) { std::reverse(myArray.begin(), myArray.end()); iterSmallest = std::min_element(myArray.begin(), myArray.end()); std::reverse(myArray.begin(), iterSmallest+1); std::reverse(iterSmallest+1, myArray.end()); } } 

Passaggio 2: scansione lineare per elementi duplicati

 for (size_t i=0, j=1; j 

Codice completo

 #include  #include  #include  #include  #include  #include  #include  #include  using namespace std; #define N 10 template  void PrintArray(const std::vector& myArray) { for (auto&& element : myArray) { std::cout << element << std::endl; } } template::value>::type* = nullptr> void RecurseOnRadixSort(std::vector& myArray, T mask, int zerosEnd, int onesBegin) { if (zerosEnd+1 >= onesBegin-1 || mask == 0) return; int zerosEnd2 = zerosEnd; int onesBegin2 = onesBegin; while(zerosEnd2+1 <= onesBegin2-1) { // swap ones to the right if ((myArray[zerosEnd2+1] & mask) != 0) { std::swap(myArray[zerosEnd2+1], myArray[onesBegin2-1]); --onesBegin2; } else ++zerosEnd2; } mask >>= 1; //recurse on lhs RecurseOnRadixSort(myArray, mask, zerosEnd, zerosEnd2+1); //recurse on rhs RecurseOnRadixSort(myArray, mask, onesBegin2-1, onesBegin); } template ::value>::type* = nullptr> void InPlaceRadixSort(std::vector& myArray) { int zerosEnd = -1; int onesBegin = static_cast(myArray.size()); T mask = static_cast(1) << sizeof(T)*8-1; while(zerosEnd+1 <= onesBegin-1) { if ( (myArray[zerosEnd+1] & mask) != 0) { std::swap(myArray[zerosEnd+1], myArray[onesBegin-1]); --onesBegin; } else ++zerosEnd; } mask = static_cast(1) << sizeof(T)*8-2; // need to reassign in case of signed datatype //recurse on lhs RecurseOnRadixSort(myArray, mask, -1, zerosEnd+1); //recurse on rhs RecurseOnRadixSort(myArray, mask, onesBegin-1, static_cast(myArray.size())); // swap negatives to the front auto iterSmallest = std::min_element(myArray.begin(), myArray.end()); if (*iterSmallest < 0) { std::reverse(myArray.begin(), myArray.end()); iterSmallest = std::min_element(myArray.begin(), myArray.end()); std::reverse(myArray.begin(), iterSmallest+1); std::reverse(iterSmallest+1, myArray.end()); } } int main() { srand(time(NULL)); std::vector myArray(N); for (size_t i=0;i 

Dimostrazione dal vivo

Ecco una soluzione interessante a questo problema con un singolo vincolo che gli elementi dovrebbero essere compresi tra 0 e n-2 (inclusi) dove n è il numero di elementi.

Funziona in tempo O (n) con una complessità di spazio O (1).

Ecco la soluzione con O (n) utilizzo del tempo e O (1) utilizzo dello spazio!

 Traverse the array. Do following for every index i of A[]. { check for sign of A[abs(A[i])] ; if positive then make it negative by A[abs(A[i])]=-A[abs(A[i])]; else // ie, A[abs(A[i])] is negative this element (ith element of list) is a repetition } 

Crediti: Metodo 5 Geek for Geeks

Questa soluzione è basata su uno che rimuove i duplicati da una matrice da @dsimcha, come può essere trovato qui .

Esegue un algoritmo di swap sul posto, con gli hash di valore utilizzati per scambiare le posizioni. Si noti che questo distrugge il contenuto dell’array originale in una certa misura. Ma non c’era alcun obbligo nella domanda dell’OP che lo proibiva.

 public static class DupFinder { public static bool HasDups(int[] array, ref int nEvals) { nEvals = 0; return DupFinder.FindInPlace(array, 0, ref nEvals); } private static bool FindInPlace(int[] array, int start, ref int nEvals) { if (array.Length - start < 2) return false; var sentinel = array[start]; var offset = start + 1; var len = array.Length - offset; for (var ndx = 0; ndx < len; nEvals++) { var cur = array[offset + ndx]; if (cur == sentinel) { ndx++; continue; } var hash = cur % len; if (ndx == hash) { ndx++; continue; } var at_hash = array[offset + hash]; if (cur == at_hash) { array[offset + ndx] = sentinel; ndx++; continue; } if (at_hash == sentinel) { Swap(array, offset, ndx, hash); ndx++; continue; } var hash_hash = at_hash % len; if (hash_hash != hash) { Swap(array, offset, ndx, hash); if (hash < ndx) ndx++; } else { ndx++; } } var swapPos = 0; for (var i = 0; i < len; i++, nEvals++) { var cur = array[offset + i]; if (cur != sentinel && i == (cur % len)) Swap(array, offset, i, swapPos++); } for (var i = swapPos; i < len; nEvals++) { var cur = array[offset + i]; if (cur == sentinel) return true; // got dups. else i++; } // Let's assume C# supports tail recursion ;-) // Then => look ma, O(1) extra storage space. return FindInPlace(array, offset + swapPos, ref nEvals); } private static void Swap(int[] array, int offset, int first, int second) { var tmp = array[offset + first]; array[offset + first] = array[offset + second]; array[offset + second] = tmp; } } 

Quindi, se supponiamo per un momento che c # supporti la ricorsione della coda e non contiamo i canvasi dello stack usati come spazio extra, ha O (1) requisiti di spazio.

L’autore lo menziona come una complessità temporale O (N). I test (limitati) (al contrario di un’analisi di complessità computazionale) che ho eseguito indicano che è più vicino a O (N log N).

 Array Size Dup Position #Evals 12 7 26 12 - 35 100,000 80,000 279,997 100,000 - 453,441 

Nel caso generale, questo problema non sembra avere una soluzione a causa dei forti vincoli di complessità e dell’input sfrenato.

È chiaro che hai bisogno di almeno N passi per VEDERE anche tutti gli input. Quindi non può essere più veloce di O(n) .

Ora, per essere sicuro di individuare ogni ansible duplicato, hai diverse possibilità:

  • Confronta ogni numero con ogni altro numero, questo non richiede molto spazio aggiuntivo, ma richiede O(n^2) tempo
  • Fai il confronto in un modo più intelligente, scambiando gli interi intorno allo spazio disponibile. Ciò consente di “memorizzare le informazioni” nella sequenza stessa. In realtà, il confronto di tutti i numeri tra loro avviene di solito in algoritmi di ordinamento . Gli algoritmi di ordinamento più veloci che non richiedono spazio aggiuntivo hanno bisogno del tempo O(n log n) . Wikipedia ha una scrittura piuttosto lunga con molte fonti . Quindi non puoi mai avere il tuo requisito di tempo in questo modo. ( alcuni grafici di confronto degli algoritmi di ordinamento noti )
  • Potresti fare un po ‘di contabilità con una mappa hash che ti permetterebbe di prendere solo il tempo lineare O(n) , ma quella contabilità deve essere immagazzinata da qualche parte . Altrimenti, semplicemente “dimenticherai” quali numeri hai già visto. Sfortunatamente, la contabilità richiederà più spazio se il tuo contributo aumenta perché hai tanti numeri diversi da ricordare. Quindi è imansible avere la stessa quantità fissa di memoria e confrontare sequenze di input arbitrariamente lunghe. Pertanto, si dovrebbe violare lo spazio costante O(1) .

Come @Atishay sottolinea nella sua risposta, ci può essere una soluzione se si dispone di un input molto limitato. Qui è necessario avere una matrice di dimensione n e i valori possibili sono solo nell’intervallo [0,n-2] . Questo requisito garantisce che DEVE esserci un duplicato da qualche parte perché ci sono meno valori diversi rispetto agli elementi dell’array. Con quella conoscenza e l’intervallo di valori molto specifico, puoi farlo. Ma questo usa ipotesi molto strette e non risolve il problema generale indicato nella domanda.

modificare

Come chiarito nei commenti, esiste un limite inferiore comprovato per la complessità temporale degli algoritmi di ordinamento basati sul confronto. Per riferimento, vedi qui:

Il filtro Bloom è un hashset efficiente in termini di spazio con un tasso falsamente positivo sintonizzabile. La falsa possibilità positiva significa che devi tornare indietro e controllare un duplicato reale quando ottieni un colpo dal BF, introducendo un termine N ^ 2 – ma il coefficiente è ~ exp (- (spazio extra usato per il filtro)). Questo produce uno spazio di scambio interessante tra spazio e tempo.

Non ho una prova che la domanda posta sia insolubile, ma in generale “ecco un interessante spazio di scambio” è una buona risposta a un problema insolubile.

un’implementazione usando un singolo int come variabile temporanea .. questo sta usando i vettori bit /

  public static boolean isUniqueChars(String str) { int checker = 0; for (int i = 0; i < str.length(); ++i) { int val = str.charAt(i) - 'a'; if ((checker & (1 << val)) > 0) return false; checker |= (1 << val); } return true; } 

o la mia implementazione precedente di O (n ^ 2) senza utilizzare alcuna variabile temporanea

 public static bool isDuplicate(char[] str) { if (str == null) return false; int len = str.length; if (len < 2) return false; for (int i = 1; i < len; ++i) { for (int j = 0; j < len; ++j) { if (str[i] == str[j]) return true; } } return false; } 

Pulisci l’esempio per determinare i duplicati con O (n) per ora e O (1) per spazio:

 public class DuplicateDetermineAlgorithm { public static boolean isContainsDuplicate(int[] array) { if (array == null) { throw new IllegalArgumentException("Input array can not be null"); } if (array.length < 2) { return false; } for (int i = 0; i < array.length; i++) { int pointer = convertToPositive(array[i]) - 1; if (array[pointer] > 0) { array[pointer] = changeSign(array[pointer]); } else { return true; } } return false; } private static int convertToPositive(int value) { return value < 0 ? changeSign(value) : value; } private static int changeSign(int value) { return -1 * value; } } 
 public static void getDuplicatesElements (Integer arr[]){ //Status array to track the elements if they are already considered boolean status[] = new boolean [arr.length]; //Flag to mark the element found its duplicate boolean dupFlag = false; //Output string String output = ""; //Count of duplicate elements found int count = 0; //Initialize status array with all false ie no duplicates for (int i = 0; i < arr.length; i++) { status[i] = false; } //first loop to check every element for (int i = 0; i < arr.length - 1; i++) { //Initialize every element to no duplicate dupFlag = false; //Check if this element is not already found duplicate, if not, check now. if (!status[i]){ for (int j = i+1; j < arr.length; j++){ if (arr[i] == arr[j]){ dupFlag = true; status[j] = true; } } } if (dupFlag){ output = output + " " + arr[i]; count++; } } System.out.println("Duplicate elements: " + output ); System.out.println("Count: " + count ); } 

disconoscimento

Non ho una risposta, ma i miei pensieri sono troppo estesi per un commento. Inoltre, volevo scriverli, quindi le tre ore che trascorro pensando a una soluzione non vanno completamente sprecate. Spero di darti un altro punto di vista, ma se non ti piace perdere tempo, non continuare a leggere. O solo giù voto questa risposta, ne vale la pena 🙂

Per dare il via al nostro pensiero visivo, disponiamo di un array di esempio: 50 100 150 -2 -1 0 1 2 3 4 . Come puoi sicuramente capire, non ha duplicati, quindi il nostro algoritmo dovrebbe generare FALSE . Inoltre, la sua lunghezza è 10 .

Fase A: contare nel tempo O (N)

Ignoriamo il vincolo di memoria extra per ora (in realtà, lo violiamo molto male, assumendo che possiamo avere O(\inf) memoria aggiuntiva 🙂 e salvare in un array infinito fittizio (è anche doppiamente infinito, dal momento che consente indivi negativi anche) i conteggi per ogni numero intero. Per il nostro input, questo array sarebbe simile a questo:

 ...000001111111000...00100...00100...001000000... ^ ^ ^ [index -2] [index 50] [index 150] 

Se uno qualsiasi degli elementi dell’array è maggiore di 1 , allora abbiamo un duplicato e l’algoritmo dovrebbe restituire TRUE .

Passo B: Map -inf..inf a 0..N in O (N)

Supponiamo di avere una mappa f(x):-inf..inf -> 0..N che può comprimere il nostro array infinito in una matrice di dimensione N, e inoltre farlo in tempo O (N). Questo è ciò che l’hashing fa idealmente. Nota che non ci interessa mantenere l’ordine dell’array, dato che ci interessa solo se ha elementi superiori a 1. Quindi, possiamo combinare questi due passaggi ed eliminare la necessità di una memoria inifinita – yay! Stiamo ancora utilizzando una memoria O (N) aggiuntiva (in realtà, esattamente N conta) per mantenere i valori del conteggio. Il prossimo passo si libererebbe di quello.

Step C: Usare il primo elemento come un interruttore

Prima di spiegare questo passaggio, notiamo che non è necessario archiviare alcun conteggio superiore a 1. La prima volta che si desidera aumentare un contatore e si nota che ha già il valore 1, sappiamo che abbiamo trovato un duplicato! Quindi 1 bit di memoria per contatore è sufficiente. Ciò riduce la memoria richiesta a O (lg (N)), ma non ci interessa molto, perché non è abbastanza buono. La parte importante è che 1 bit di memoria per contatore è sufficiente.

Ora stiamo andando a sfruttare il fatto che possiamo modificare il nostro array di input. Andiamo sulla matrice e su tutti gli elementi con il valore del primo elemento. Se il risultato è inferiore al valore precedente all’operazione, lo cambiamo in tale risultato. Memorizziamo anche il primo elemento separatamente come sw con un costo di memoria O (1) aggiuntivo.

Ora, possiamo usare il primo elemento memorizzato sw e l’array trasformato per codificare i conteggi dal passo di conteggio (passi A + B) nel modo seguente: considerando l’elemento con l’indice k A , se A[f(A[k])] < A[f(A[k])] xor sw allora il conteggio è zero che significa che l'elemento che stiamo considerando - A[k] - non è stato visto prima, quindi cambieremo A[f(A[k])] a A[f(A[k])] xor sw . Se, altrimenti, A[f(A[k])] > A[f(A[k])] xor sw allora il conteggio è one che significa che l'elemento che stiamo considerando - A[k] - è già stato visto prima , quindi è un duplicato.

Supponendo la mappa:

 f(-2 xr 50) -> 0 f(-1 xr 50) -> 1 f(0) -> 2 f(1) -> 3 f(2) -> 4 f(3) -> 5 f(4) -> 6 f(86) -> 7 f(150) -> 8 f(1337) -> 9 

e dopo aver eseguito i passaggi nel seguente ordine: step c; step a+b step c; step a+b l'array di input ha il seguente aspetto:

 50(0) 100(86) 150(164) -2(-2 xr 50) -1(-1 xr 50) 0(50) 1(51) 2(48) 3(49) 4(54) [intermediate state, not stored in memory] 0 86 150 -2 xr 50 -1 xr 50 0 1 2 3 4 [state after step c] 0 86 *164* -2 xr 50 -1 xr 50 0 1 2 3 4 [counted element 0] 0 86 164 -2 xr 50 -1 xr 50 0 1 *48* 3 4 [counted element 1] 0 86 164 -2 xr 50 -1 xr 50 0 1 48 *49* 4 [counted element 2] *50* 86 164 -2 xr 50 -1 xr 50 0 1 48 49 4 [counted element 3] 50 *100* 164 -2 xr 50 -1 xr 50 0 1 48 49 4 [counted element 4] 50 100 !164! -2 xr 50 -1 xr 50 0 1 48 49 4 [counted element 5] 

Cercando di contare l'elemento con l'indice 5 che è 0 , vediamo che c'era già uno 0 nell'array! (poiché A[f(A[5])] è 164 che è maggiore di 164 xr 50 ). Quindi, emettiamo TRUE e l'algoritmo termina.

Morale della storia

Se non ci è concesso abbastanza memory x time siamo costretti a dimenticare qualcosa e fare un errore.

scusate

Sfortunatamente, non abbiamo una perfetta funzione di hash, e non possiamo semplicemente creare memoria dal nulla, quindi un approccio tradizionale non funzionerebbe sotto i vincoli richiesti. L'algoritmo che la risposta fornita OP indica potrebbe essere modificato in modo tale da consentire l'uso di numeri che interpretati come indi di matrice non rientrino nei limiti dell'array, data una perfetta funzione di hash. Ma anche allora, bisogna inventarsi come usarlo per rilevare la duplicazione, piuttosto che trovarne uno garantito per esistere ...

Ad ogni modo, un problema interessante.

 import java.util.HashSet; import java.util.Set; public class FindDups { public static void main(String[] args) { int a[]={1,2,3,3,4}; Set s=new HashSet(); for(int i=0;i