Trova i due elementi ripetuti in un determinato array

Question

Viene fornita una matrice di n + 2 elementi. Tutti gli elementi dell'array sono nell'intervallo da 1 a n. E tutti gli elementi si verificano una volta tranne due numeri che si verificano due volte. Trova i due numeri ripetuti.

Per esempio, un array = {4, 2, 4, 5, 2, 3, 1} e n = 5

ragazzi che conosco 4 soluzioni probabili a questo problema, ma di recente ho incontrato una soluzione che io sono non in grado di interpretare Sotto è un algoritmo per la soluzione

traverse the list for i= 1st to n+2 elements 
{ 
check for sign of A[abs(A[i])] ; 
if positive then 
    make it negative by A[abs(A[i])]=-A[abs(A[i])]; 
else // i.e., A[abs(A[i])] is negative 
    this element (ith element of list) is a repetition 
} 
Example: A[] = {1,1,2,3,2} 
i=1 ; A[abs(A[1])] i.e,A[1] is positive ; so make it negative ; 
so list now is {-1,1,2,3,2} 

i=2 ; A[abs(A[2])] i.e., A[1] is negative ; so A[i] i.e., A[2] is repetition, 
now list is {-1,1,2,3,2} 

i=3 ; list now becomes {-1,-1,2,3,2} and A[3] is not repeated 
now list becomes {-1,-1,-2,3,2} 

i=4 ; 
and A[4]=3 is not repeated 

i=5 ; we find A[abs(A[i])] = A[2] is negative so A[i]= 2 is a repetition, 

This method modifies the original array. 

come questo algoritmo sta producendo risultati corretti cioè come sia working.Guys non prendere questo come un Homework domanda come la questione è stata recentemente chiesto a Intervista di Microsoft

Answer 1

Viene fornita una matrice di n + 2 elementi . Tutti gli elementi dell'array sono nell'intervallo da 1 a n. E tutti gli elementi si verificano una volta, tranne due numeri che si verificano due volte

Lets modificare questo un po ', e andare con solo n, non n+2, e la prima parte della dichiarazione del problema, diventa

Viene fornita una serie di n elementi . Tutti gli elementi dell'array sono nella gamma da 1 a n

Così ora sai di avere una matrice, i numeri nella matrice partono da 1 e andare da uno per ogni elemento dell'array. Quindi se hai 10 articoli, la matrice conterrà i numeri da 1 a 10. 5 articoli, hai da 1 a 5 e così via.

Ne consegue che i numeri memorizzati nell'array possono essere utilizzati per indicizzare l'array. Ad esempio, puoi sempre dire A[A[i]] dove i < = dimensione di A. ad es. A={5,3,4,1,2}; print A[A[2]]

Ora, consente di aggiungere un numero duplicato. L'algoritmo prende il valore di ciascun numero nell'array e visita quell'indice. Sappiamo che se visitiamo lo stesso indice due volte, sappiamo di aver trovato un duplicato.
Come facciamo a sapere se visitiamo lo stesso indice due volte?
Sì, cambiamo il segno del numero in ogni indice che visitiamo, se il segno è già cambiato, sappiamo che siamo già stati qui, ergo, questo indice (non il valore memorizzato nell'indice) è un numero duplicato .

È possibile ottenere lo stesso risultato mantenendo una seconda matrice di valori booleani inizializzata su false. Che algroithm diventa

A={123412} 
B={false, false, false, false} 

for(i = 1; i <= 4; i++) 
{ 
    if(B[A[i]]) 
     // Duplicate 
    else 
     B[A[i]] = true; 
} 

Tuttavia nella questione MS si sta cambiando il segno dell'elemento in A invece di impostare un valore booleano in B.

Spero che questo aiuti,

Answer 2

Quello che stai facendo è usare i valori dell'array in due modi: hanno un numero E hanno un segno. Si "memorizza" il fatto che si è visto un numero n nell'n-esimo punto dell'array, senza perdere il valore originale in quel punto: si sta solo cambiando il segno.

Si inizia con tutti i positivi, e se si scopre che il proprio indice si desidera "salvare" il fatto che si è visto il valore corrente è già negativo, allora questo valore è già visibile.

esempio: Quindi se si vede 4 per la prima volta, si modifica il segno sul quarto punto in negativo. Questo non cambia il 4 ° punto, perché stai usando [abs] su quello quando andresti lì, quindi non preoccuparti. Se vedi altri 4, controlli di nuovo il 4 ° punto, vedi che è negativo: presto: un doppio.

Answer 3

Quando si trova un elemento in posizione i, diciamo n, quindi si produce A[abs(A(i))]=A[abs(n)] negativo. Quindi se trovi un'altra posizione j contenente n, controllerai anche A[abs(A(j))]=A[abs(n)]. Dal momento che lo trovi negativo, allora n viene ripetuto :)

Answer 4

Semplice, l'uso un Hashtable.

Per ogni articolo, verificare se esiste già O (1), e in caso contrario, aggiungerlo alla tabella hash O (1).

Quando trovi un articolo già esistente ... il gioco è fatto.

Answer 5

So che questa non è davvero una risposta alla tua domanda, ma se dovessi scrivere questo codice su un progetto reale, inizierei con una sorta di quicksort, e nella mia funzione di confronto qualcosa come

int Compare(int l, int r) 
{ 
    if(l == r) 
    { 
     // duplicate; insert into duplicateNumbers array if it doesn't exist already. 
     // if we found 2 dupes, quit the sort altogether 
    } 
    return r - l; 
} 

Vorrei archiviarlo nel "buon equilibrio tra prestazioni e manutenibilità" benna di possibili soluzioni.