Mi è stato chiesto in un'intervista di fornire un algoritmo O (n) per stampare un elemento che appare più di n/2 volte in un array, se c'è un tale elemento. n è la dimensione dell'array. Non ho idea di come farlo. Qualcuno può aiutare?O (n) algoritmo per scoprire l'elemento che appare più di n/2 volte
È il Boyer's Voting algorithm.
È anche O (1) nello spazio !.
Modifica
Per coloro che si lamentano la combinazione di colori sito (come me) ... here is the original paper.
La combinazione di colori su quel link è orribile. –
Ecco alcune ulteriori informazioni: http://stackoverflow.com/questions/780937/linear-time-voting-algorithm-i-dont-get-it – chrisaycock
Bella lettura. Mi ci è voluto un minuto per trovare la logica sottile che evita di mantenere i conteggi indipendenti: "..._ incrementa o decrementa il contatore_ a seconda che e sia l'attuale candidato ..." –
In psuedocodarlo:
int n = array.length
Hash<elementType,int> hash
foreach element in array
hash[element] += 1
foreach entry in hash
if entry.value > n/2
print entry.key
break
Questo non dovrebbe essere considerato O (2n)? –
O (2n) == O (n) credo – Samuel
@Eric Questo sarebbe 'O (n + m)'. A proposito, non esiste qualcosa come "O (2n)' come grande-O non usa coefficienti costanti; in tal caso è solo 'O (n)'. – chrisaycock
E 'anche il valore mediano, che prende O (n) per trovare utilizzando il median-of-medians algorithm. In C++ puoi farlo in una riga:
std::nth_element(begin, begin + n/2, begin + n)
Si noti tuttavia che 'std :: nth_element' è richiesto solo per essere previsto O (n) e quindi probabilmente non usa l'algoritmo mediano-di-mediani. La selezione rapida come la selezione tende ad essere migliore in pratica rispetto alla m-of-m. –
È sufficiente utilizzare un hash e contare il numero di elementi durante la scansione attraverso l'array? – chrisaycock
Non sicuro. Penso che ci dovrebbe essere una soluzione più semplice ed elegante. – devnull
Oh. Non hai chiesto il più elegante, solo O (n) – Samuel