Un algoritmo di intervista di Google interessante che ho trovato online che richiede tempo lineare

Question

Quindi ho trovato questa domanda di algoritmo di intervista di Google online. È davvero interessante e non ho ancora trovato una buona soluzione. Si prega di dare un'occhiata, e mi danno un suggerimento/soluzione, sarebbe bello se è possibile scrivere il codice in Java :).

"Progettare un algoritmo che, dato un elenco di n elementi in un array, trova tutti gli elementi che appaiono più di n/3 volte nell'elenco. L'algoritmo deve essere eseguito in tempo lineare. (N> = 0) Si sono tenuti a utilizzare il confronto e raggiungere il tempo lineare No hashing/spazio eccessivo/e non si utilizza standard di tempo lineare selezione deterministica algo"

Answer 1

Suggerimento:. Guardate Boyer and Moore's Linear Time Voting Algorithm

Meglio Suggerimento: Pensate a risolvere il problema di maggioranza prima. Cioè, prova a trovare un elemento che si verifica almeno n/2 volte. L'idea di base dell'algoritmo è se cancelliamo ogni occorrenza di un elemento e con tutti gli altri elementi che sono diversi da e quindi e esisterà fino alla fine se è un elemento di maggioranza.

findCandidate(a[], size) 
    //Initialize index and count of majority element 
    maj_index = 0; 
    count = 1; 

    for i = 1 to n–1 { 
     if a[maj_index] == a[i] 
      count++; 
     else 
      count--; 

     if count == 0 { 
      maj_index = i; 
      count = 1; 
     } 
    } 
    return a[maj_index] 

Questo algoritmo scorre ogni elemento e mantiene un conteggio di a[maj_index]. Se l'elemento successivo è lo stesso, incrementa il conteggio, se l'elemento successivo non è lo stesso, decrementa il conteggio e se il conteggio raggiunge 0, modifica maj_index nell'elemento corrente e imposta il conteggio su 1.

Avanti devi controlla che questo elemento si verifichi effettivamente almeno n/2 volte, ma ciò può essere fatto in un unico passaggio.

Answer 2

La mia soluzione è stata ispirata dal gioco Tetris. Evidenziazione soluzione (doppiata come 'processo Tetrise'): utilizza tre coppie chiave-valore per la contabilità, con chiave l'elemento, valore il conteggio dell'elemento. In un ciclo principale, conserviamo al massimo 3 ultimi elementi distinti. Quando il conteggio di tutte e tre le chiavi è diverso da zero, decrementiamo i conteggi di tutti ed eliminiamo le eventuali chiavi con zero-count. Alla fine, potrebbero esserci o non essere alcuni elementi residui. Questi sono i sopravvissuti al processo di Tetris. Nota che non ci possono essere più di 3 elementi residui. Se non viene lasciato nulla, restituiamo null. Altrimenti passiamo in rassegna gli elementi originali n, contando il numero di questi elementi residui e restituendo quelli il cui conteggio è> n/3.

Suggerimento: Per mostrare la correttezza dell'algoritmo di cui sopra, si noti che per un elemento deve sopravvivere al processo Tetris o rimanere nel residuo per soddisfare il requisito. Per capire perché, denotiamo il numero di operazioni di rimozione come m e il conteggio totale degli elementi residui r. Quindi abbiamo n = 3 * m + r. Da qui otteniamo m < = n/3, perché r> = 0. Se un elemento non è sopravvissuto al processo Tetrise, l'occorrenza massima che può apparire è m < = n/3.

Tempo complessità O (n), complessità spaziale O (1).