Trova l'elemento non duplicati in un array ordinato

Question

Fonte: Intervista Microsoft Domanda

Dato un array ordinato, in cui ogni elemento è presente due volte, tranne uno che è presente getta, abbiamo bisogno di trovare quell'elemento .

Ora un O standard (n) la soluzione è di fare un XOR di lista, che restituirà l'elemento non duplicati (dal momento che tutti gli elementi duplicati si annullano.)

E 'possibile risolvere il più rapidamente se sappiamo l'array è ordinato?

Answer 1

Sì, è possibile utilizzare il sortedness di ridurre la complessità a O(log n) facendo una ricerca binaria.

Poiché la matrice è ordinata, prima dell'elemento mancante, ciascun valore occupa gli spot 2*k e 2*k+1 nell'array (presupponendo l'indicizzazione basata su 0).

Così si va al centro della matrice, dire indice di h, e controllare sia indice di h+1 se h è ancora, o se h-1h è dispari. Se l'elemento mancante viene dopo, i valori in queste posizioni sono uguali, se viene prima, i valori sono diversi. Ripeti fino a trovare l'elemento mancante.

Answer 2

Esegui una "ricerca" binaria (piuttosto trasversale) sull'array, controlla entrambi i vicini, se entrambi sono diversi dal valore nel mezzo, hai la soluzione. Questo è O(log n).