Come trovare un elemento duplicato in una matrice di numeri interi consecutivi mescolati?

Recentemente ho trovato una domanda da qualche parte:

Supponiamo di avere una matrice di 1001 numeri interi. Gli interi sono in ordine casuale, ma sai che ognuno degli interi è compreso tra 1 e 1000 (inclusi). Inoltre, ogni numero appare solo una volta nell’array, ad eccezione di un numero, che si verifica due volte. Supponiamo che tu possa accedere ad ogni elemento dell’array solo una volta. Descrivi un algoritmo per trovare il numero ripetuto. Se hai usato la memoria ausiliaria nell’algoritmo, puoi trovare un algoritmo che non lo richiede?

Quello che mi interessa sapere è la seconda parte , cioè, senza usare la memoria ausiliaria . Hai qualche idea?

Basta aggiungerli tutti e sottrarre il totale che ci si aspetterebbe se venissero utilizzati solo 1001 numeri.

Per esempio:

Input: 1,2,3,2,4 => 12 Expected: 1,2,3,4 => 10 Input - Expected => 2 

Aggiornamento 2: alcune persone pensano che l’uso di XOR per trovare il numero duplicato sia un trucco o un trucco. A cui la mia risposta ufficiale è: “Non sto cercando un numero duplicato, sto cercando un modello duplicato in una serie di bit set e XOR è decisamente più adatto di ADD per manipolare i bit set”. 🙂

Aggiornamento: solo per divertimento prima di andare a letto, ecco la soluzione alternativa “a una linea” che richiede zero storage aggiuntivo (nemmeno un contatore di loop), tocca ogni elemento dell’array una sola volta, non è distruttivo e non scala affatto: -)

 printf("Answer : %d\n", array[0] ^ array[1] ^ array[2] ^ // continue typing... array[999] ^ array[1000] ^ 1 ^ 2 ^ // continue typing... 999^ 1000 ); 

Si noti che il compilatore calcolerà la seconda parte dell’espressione in fase di compilazione, quindi l’algoritmo verrà eseguito esattamente in 1002 operazioni.

E se i valori degli elementi dell’array sono noti anche al momento della compilazione, il compilatore ottimizzerà l’intera istruzione su una costante. 🙂

Soluzione originale: che non soddisfa i severi requisiti delle domande, anche se funziona per trovare la risposta corretta. Usa un intero aggiuntivo per mantenere il contatore del ciclo e accede a ciascun elemento dell’array tre volte, due volte per leggerlo e scriverlo durante l’iterazione corrente e una volta per leggerlo per l’iterazione successiva.

Bene, è necessario almeno una variabile aggiuntiva (o un registro CPU) per memorizzare l’indice dell’elemento corrente mentre si passa attraverso l’array.

A parte questo, però, ecco un algoritmo distruttivo che può scalare in modo sicuro da qualsiasi N fino a MAX_INT.

 for (int i = 1; i < 1001; i++) { array[i] = array[i] ^ array[i-1] ^ i; } printf("Answer : %d\n", array[1000]); 

Lascerò l'esercizio di capire perché questo ti funziona, con un semplice suggerimento :-):

 a ^ a = 0 0 ^ a = a 

Una versione non distruttiva della soluzione di Franci Penov.

Questo può essere fatto usando l’operatore XOR .

Diciamo che abbiamo una serie di dimensioni 5 : 4, 3, 1, 2, 2
Quali sono nell’indice: 0, 1, 2, 3, 4

Ora fai un XOR di tutti gli elementi e di tutti gli indici. Otteniamo 2 , che è l’elemento duplicato. Questo accade perché, 0 non ha alcun ruolo nello XORing. Gli altri indici n-1 accoppiano con gli stessi elementi n-1 nella matrice e l’ unico elemento non appaiato nella matrice sarà il duplicato.

 int i; int dupe = 0; for(i = 0; i < N; i++) { dupe = dupe ^ arr[i] ^ i; } // dupe has the duplicate. 

La migliore caratteristica di questa soluzione è che non soffre di problemi di overflow che si riscontrano nella soluzione basata sull'aggiunta.

Poiché si tratta di una domanda di intervista, sarebbe meglio iniziare con la soluzione basata sull'aggiunta, identificare la limitazione dell'overflow e quindi fornire la soluzione basata su XOR :)

Questo fa uso di una variabile aggiuntiva quindi non soddisfa completamente i requisiti della domanda.

Aggiungi tutti i numeri insieme. La sum finale sarà il numero 1 + 2 + … + 1000 + duplicato.

Parafrasando la soluzione di Francis Penov.

Il (solito) problema è: dato un array di numeri interi di lunghezza arbitraria che contengono solo elementi ripetuti un numero pari di volte eccetto per un valore che viene ripetuto un numero dispari di volte, trova questo valore.

La soluzione è:

 acc = 0 for i in array: acc = acc ^ i 

Il tuo problema attuale è un adattamento. Il trucco è che devi trovare l’elemento che viene ripetuto due volte, quindi devi adattare la soluzione per compensare questa stranezza.

 acc = 0 for i in len(array): acc = acc ^ i ^ array[i] 

Qual è la soluzione di Francis alla fine, anche se distrugge l’intero array (a proposito, potrebbe solo distruggere il primo o l’ultimo elemento …)

Ma dal momento che hai bisogno di una memoria extra per l’indice, penso che ti verrà perdonato se usi anche un numero intero in più … La restrizione è probabilmente perché vogliono impedirti di utilizzare un array.

Sarebbe stato formulato in modo più preciso se avessero richiesto lo spazio O(1) (1000 può essere visto come N dato che qui è arbitrario).

Aggiungi tutti i numeri. La sum di interi 1..1000 è (1000 * 1001) / 2. La differenza da ciò che ottieni è il tuo numero.

Se sai che abbiamo i numeri esatti 1-1000, puoi sumre i risultati e sottrarre 500500 ( sum(1, 1000) ) dal totale. Questo darà il numero ripetuto perché sum(array) = sum(1, 1000) + repeated number .

Bene, c’è un modo molto semplice per farlo … ognuno dei numeri tra 1 e 1000 si verifica esattamente una volta tranne il numero che viene ripetuto …. quindi, la sum da 1 a 1000 è 500500. Quindi, l’algoritmo è:

 sum = 0
 per ogni elemento dell'array:
    sum + = quell'elemento dell'array
 number_that_occurred_twice = sum - 500500

Una soluzione di linea in Python

 arr = [1,3,2,4,2] print reduce(lambda acc, (i, x): acc ^ i ^ x, enumerate(arr), 0) # -> 2 

Spiegazione del motivo per cui funziona è nella risposta di @Matthieu M.

 n = 1000 s = sum(GivenList) r = str(n/2) duplicate = int( r + r ) - s 
 public static void main(String[] args) { int start = 1; int end = 10; int arr[] = {1, 2, 3, 4, 4, 5, 6, 7, 8, 9, 10}; System.out.println(findDuplicate(arr, start, end)); } static int findDuplicate(int arr[], int start, int end) { int sumAll = 0; for(int i = start; i <= end; i++) { sumAll += i; } System.out.println(sumAll); int sumArrElem = 0; for(int e : arr) { sumArrElem += e; } System.out.println(sumArrElem); return sumArrElem - sumAll; } 

Nessun requisito di archiviazione aggiuntivo (a parte la variabile loop).

 int length = (sizeof array) / (sizeof array[0]); for(int i = 1; i < length; i++) { array[0] += array[i]; } printf( "Answer : %d\n", ( array[0] - (length * (length + 1)) / 2 ) ); 

Gli argomenti e i callstacks contano come memoria ausiliaria?

 int sumRemaining(int* remaining, int count) { if (!count) { return 0; } return remaining[0] + sumRemaining(remaining + 1, count - 1); } 
 printf("duplicate is %d", sumRemaining(array, 1001) - 500500); 

Modifica: versione chiamata coda

 int sumRemaining(int* remaining, int count, int sumSoFar) { if (!count) { return sumSoFar; } return sumRemaining(remaining + 1, count - 1, sumSoFar + remaining[0]); } printf("duplicate is %d", sumRemaining(array, 1001, 0) - 500500); 
 public int duplicateNumber(int[] A) { int count = 0; for(int k = 0; k < A.Length; k++) count += A[k]; return count - (A.Length * (A.Length - 1) >> 1); } 

Un triangolo numero T (n) è la sum dei n numeri naturali da 1 a n. Può essere rappresentato come n (n + 1) / 2. Quindi, sapendo che tra i 1001 numeri naturali dati, uno e un solo numero è duplicato, puoi sumre facilmente tutti i numeri dati e sottrarre T (1000). Il risultato conterrà questo duplicato.

Per un numero triangular T (n), se n è una potenza di 10, c’è anche un bellissimo metodo che trova questo T (n), basato sulla rappresentazione in base 10:

 n = 1000 s = sum(GivenList) r = str(n/2) duplicate = int( r + r ) - s 

Sostengo l’aggiunta di tutti gli elementi e quindi sottraendo da essa la sum di tutti gli indici, ma questo non funzionerà se il numero di elementi è molto grande. Cioè causerà un overflow intero! Quindi ho ideato questo algoritmo che potrebbe ridurre le possibilità di un overflow di interi in larga misura.

  for i=0 to n-1 begin: diff = a[i]-i; dup = dup + diff; end // where dup is the duplicate element.. 

Ma con questo metodo non sarò in grado di trovare l’indice al quale è presente l’elemento duplicato!

Per quello ho bisogno di attraversare la matrice un altro tempo che non è desiderabile.

Miglioramento della risposta di Fraci in base alla proprietà dei valori consecutivi di XORing:

 int result = xor_sum(N); for (i = 0; i < N+1; i++) { result = result ^ array[i]; } 

Dove:

 // Compute (((1 xor 2) xor 3) .. xor value) int xor_sum(int value) { int modulo = x % 4; if (modulo == 0) return value; else if (modulo == 1) return 1; else if (modulo == 2) return i + 1; else return 0; } 

O in pseudocode / math lang f (n) definito come (ottimizzato):

 if n mod 4 = 0 then X = n if n mod 4 = 1 then X = 1 if n mod 4 = 2 then X = n+1 if n mod 4 = 3 then X = 0 

E in forma canonica f (n) è:

 f(0) = 0 f(n) = f(n-1) xor n 

La mia risposta alla domanda 2:

Trova la sum e il prodotto dei numeri da 1 – (a) N, ad esempio SUM , PROD .

Trova la sum e il prodotto di Numbers da 1 – N- x -y, (presumo x, y mancante), ad esempio mySum, myProd,

Così:

 SUM = mySum + x + y; PROD = myProd* x*y; 

Così:

 x*y = PROD/myProd; x+y = SUM - mySum; 

Possiamo trovare x, y se risolvi questa equazione.