Individuazione dell'elemento duplicato in una matrice

Question

Esiste una matrice di dimensione n e gli elementi contenuti nella matrice sono compresi tra 1 e n-1 in modo che ogni elemento si verifichi una sola volta e un solo elemento si verifichi più volte. Dobbiamo trovare questo elemento.

Sebbene questa sia una FAQ molto frequente, non ho ancora trovato una risposta adeguata. La maggior parte dei suggerimenti è che dovrei sommare tutti gli elementi dell'array e quindi sottrarre da esso la somma di tutti gli indici, ma questo non funzionerà se il numero di elementi è molto grande. Traboccherà. Ci sono stati anche suggerimenti riguardanti l'uso della porta XOR dup = dup^arr[i]^i, che per me non sono chiari.

Sono arrivato a questo algoritmo che è un miglioramento dell'algoritmo di addizione e ridurrà in gran parte le possibilità di overflow!

for i=0 to n-1 
    begin : 
    diff = A[i] - i; 
    sum = sum + diff; 
    end 

diff contiene l'elemento duplicato, ma con questo metodo non sono in grado di scoprire l'indice dell'elemento duplicato. Per quello ho bisogno di attraversare ancora una volta l'array che non è desiderabile. Qualcuno può trovare una soluzione migliore che non implichi il metodo di addizione o che il metodo XOR funzioni in O (n)?

Answer 1

Esistono molti modi per pensare a questo problema, in base ai vincoli della descrizione del problema.

Se si sa per certo che esattamente un elemento è duplicato, ci sono molti modi per risolvere questo problema. Una soluzione particolarmente intelligente è l'uso dell'operatore XOR bit a bit. XOR ha le seguenti proprietà interessanti:

1. XOR è associativa, quindi (x^y)^z = x^(y^z)
2. XOR è commutativo: x^y = y^x
3. XOR è proprio inversa: x^y = 0 se e solo se x = y
4. XOR ha zero come identità: x^0 = x

Properties (1) e (2) qui significa che quando prende il XOR di un gruppo di valori, non importa quale ordine si applicano gli XOR agli elementi. Puoi riordinare gli elementi o raggrupparli come meglio credi. Proprietà (3) significa che se si XOR lo stesso valore insieme più volte, si ottiene zero zero, e la proprietà (4) significa che se si XOR qualsiasi cosa con 0 si ottiene il numero originale. Prendendo tutte queste proprietà insieme, ottieni un risultato interessante: se prendi lo XOR di un gruppo di numeri, il risultato è lo XOR di tutti i numeri nel gruppo che appaiono un numero dispari di volte. Il motivo è che quando numeri XOR che compaiono un numero pari di volte, puoi spezzare lo XOR di quei numeri in un insieme di coppie. Ogni coppia di XOR a 0 di (3) e la combinazione di XOR di tutti questi zeri restituiscono zero di (4). Di conseguenza, tutti i numeri di molteplicità pari si annullano.

Per utilizzare questo per risolvere il problema originale, effettuare le seguenti operazioni. Innanzitutto, XOR raggruppa tutti i numeri nell'elenco. Questo dà lo XOR di tutti i numeri che appaiono un numero dispari di volte, che finisce per essere tutti i numeri da 1 a (n-1) eccetto il duplicato. Ora, XOR questo valore con lo XOR di tutti i numeri da 1 a (n-1). Quindi, tutti i numeri compresi nell'intervallo 1 a (n-1) che non erano stati cancellati in precedenza si cancellano, lasciando solo il valore duplicato. Inoltre, questo viene eseguito in tempo O (n) e utilizza solo lo spazio O (1), poiché lo XOR di tutti i valori si inserisce in un singolo numero intero.

Nel tuo post originale hai considerato un approccio alternativo che funziona utilizzando il fatto che la somma degli interi da 1 a n-1 è n (n-1)/2.Tuttavia, era preoccupato che ciò avrebbe comportato un overflow dei numeri interi e causato un problema. Sulla maggior parte delle macchine hai ragione che ciò causerebbe un overflow, ma (sulla maggior parte delle macchine) questo non è un problema perché l'aritmetica viene eseguita usando numeri interi a precisione fissa, comunemente numeri interi a 32 bit. Quando si verifica un overflow di un intero, il numero risultante non è privo di significato. Piuttosto, è solo il valore che si otterrebbe se si calcolasse il risultato effettivo, quindi si eliminasse tutto tranne i 32 bit più bassi. Matematicamente parlando, questo è noto come aritmetica modulare, e le operazioni nel computer sono fatte modulo 2 . Più in generale, però, diciamo che gli interi sono memorizzati in modulo k per alcuni k fissi.

Fortunatamente, molte delle leggi aritmetiche che si conoscono e si amano dalla normale aritmetica sono ancora valide nell'aritmetica modulare. Dobbiamo solo essere più precisi con la nostra terminologia. Diciamo che x è congruente a y modulo k (denotato x ≡ _k y) se x e y lasciano lo stesso resto quando sono divisi per k. Questo è importante quando si lavora su una macchina fisica, perché quando si verifica un overflow di un intero sulla maggior parte dell'hardware, il valore risultante è congruente al valore vero modulo k, dove k dipende dalla dimensione della parola. Fortunatamente, le seguenti leggi valgono in aritmetica modulare:

Ad esempio:

1. Se x ≡ _k y e w ≡ _k z, x + w ≡ _k y + z
2. Se x ≡ _k y e w ≡ _k z, allora xw ≡ _k yz.

Questo significa che se si vuole calcolare il valore duplicato trovando la somma totale degli elementi della matrice e sottraendo il totale previsto, tutto andrà bene, anche se v'è un integer overflow causa l'aritmetica di serie continuerà a produrre gli stessi valori (modulo k) nell'hardware. Detto questo, puoi anche utilizzare l'approccio basato su XOR, che non deve assolutamente considerare l'overflow. :-)

Se non si è certi che esattamente un elemento è duplicato, ma è possibile modificare l'array di elementi, c'è un bellissimo algoritmo per trovare il valore duplicato. This earlier SO question descrive come eseguire questa operazione. Intuitivamente, l'idea è di provare a ordinare la sequenza usando uno bucket sort, in cui l'array di elementi viene riciclato per contenere anche lo spazio per i bucket.

Se non si è certi che esattamente un elemento è duplicato e non è possibile modificare l'array di elementi, il problema è molto più difficile. Si tratta di un classico (e difficile!) Problema di intervista che, secondo quanto riferito, ha impiegato Don Knuth 24 ore per risolverlo. Il trucco è di ridurre il problema a un'istanza di cycle-finding trattando l'array come una funzione dai numeri 1-n su 1- (n-1) e quindi cercando due ingressi per quella funzione. Tuttavia, l'algoritmo risultante, chiamato Floyd's cycle-finding algorithm, è estremamente bello e semplice. È interessante notare che è lo stesso algoritmo che usereste per rilevare un ciclo in una lista collegata in tempo lineare e spazio costante. Consiglierei di cercarlo, poiché viene periodicamente inserito nelle interviste software.

Per una descrizione completa dell'algoritmo anche un'analisi, prova di correttezza e implementazione di Python, controllare this implementation che risolve il problema.

Spero che questo aiuti!

Answer 2

L'aggiunta degli elementi è perfetta, basta prendere il mod (%) dell'aggregato intermedio per calcolare la somma degli elementi e la somma prevista. Per l'operazione mod puoi usare qualcosa come 2n. Devi anche aggiustare il valore dopo la sottrazione.