Trova la voce più comune in un array

Question

Viene fornito un array intero senza segno a 32 bit con lunghezza fino a 2 ³² , con la proprietà che più della metà delle voci nell'array sono uguali a N, per alcuni 32-bit numero intero senza segno N. Trova N guardando ogni numero nell'array una sola volta e usando al massimo 2 kB di memoria.

La tua soluzione deve essere deterministica e garantita per trovare N.

Answer 1

Mantieni un numero intero per ogni bit e incrementa questa raccolta in modo appropriato per ogni numero intero nella matrice.

Alla fine, alcuni dei bit avranno un conteggio superiore alla metà della lunghezza dell'array - quei bit determinano N. Naturalmente, il conteggio sarà maggiore del numero di volte in cui si è verificato N, ma ciò non accade importa. La cosa importante è che qualsiasi bit che non fa parte di N non può ricorrere più della metà delle volte (poiché N ha oltre la metà delle voci) e qualsiasi bit che fa parte di N deve si verificano più della metà delle volte (perché accadrà ogni volta che si verifica N e qualsiasi extra).

(Nessun codice al momento - sta per perdere l'accesso alla rete. Speriamo che quanto sopra sia abbastanza chiaro però.)

Answer 2

Boyer and Moore's " Linear Time Majority Vote Algorithm " ; - passa in basso l'array mantenendo la tua ipotesi attuale sulla risposta.

Answer 3

Puoi farlo con solo due variabili.

public uint MostCommon(UInt32[] numberList)
{
    uint suspect = 0;
    int suspicionStrength = -1; 
    foreach (uint number in numberList)
    {
        if (number==suspect)
        {
            suspicionStrength++;
        }
        else
        {
            suspicionStrength--;
        }

        if (suspicionStrength<=0)
        {
            suspect = number;
        }
    }
    return suspect;
}

Imposta il primo numero come numero sospetto e continua a scorrere l'elenco. Se il numero corrisponde, aumenta la forza del sospetto di uno; se non corrisponde, riduci di uno il livello di sospetto. Se l'intensità del sospetto raggiunge 0, il numero corrente diventa il numero sospetto. Questo non funzionerà per trovare il numero più comune, solo un numero che supera il 50% del gruppo. Resistete alla tentazione di aggiungere un segno di spunta se suspicionStrength è maggiore della metà della lunghezza dell'elenco - si tradurrà sempre in un confronto più totale.

P.S. Non ho testato questo codice: utilizzalo a tuo rischio e pericolo.

Answer 4

Pseudo codice (blocco note C ++ :-)) per l'algoritmo di Jon:

int lNumbers = (size_of(arrNumbers)/size_of(arrNumbers[0]);

for (int i = 0; i < lNumbers; i++)
  for (int bi = 0; bi < 32; bi++)
    arrBits[i] = arrBits[i] + (arrNumbers[i] & (1 << bi)) == (1 << bi) ? 1 : 0;

int N = 0;

for (int bc = 0; bc < 32; bc++)
  if (arrBits[bc] > lNumbers/2)
    N = N | (1 << bc);

Answer 5

Notare che se la sequenza a0, a1,. . . , un - 1 contiene un leader, quindi dopo aver rimosso una coppia di elementi di valori diversi, la sequenza rimanente ha ancora lo stesso leader. Anzi, se noi rimuovere due elementi diversi, quindi solo uno di essi potrebbe essere il leader. Il leader nel la nuova sequenza si verifica più di n / 2 - 1 = (n - 2) / 2 volte. Di conseguenza, è ancora il leader del nuova sequenza di elementi n - 2 .

Ecco un'implementazione di Python, con complessità temporale O (n):

def goldenLeader(A):
    n = len(A)
    size = 0
    for k in xrange(n):
        if (size == 0):
            size += 1
            value = A[k]
        else:
            if (value != A[k]):
                size -= 1
            else:
                size += 1
    candidate = -1
    if (size > 0):
        candidate = value
    leader = -1
    count = 0
    for k in xrange(n):
        if (A[k] == candidate):
            count += 1
    if (count > n // 2):
        leader = candidate
    return leader

Answer 6

Questo è un problema standard negli algoritmi di streaming (dove hai un enorme (potenzialmente infinito) flusso di dati) e devi calcolare alcune statistiche da questo flusso, passando attraverso questo flusso una volta.

---

Chiaramente puoi affrontarlo con hashing o ordinamento, ma con un flusso potenzialmente infinito esaurisci chiaramente la memoria. Quindi devi fare qualcosa di intelligente qui.

---

L'elemento di maggioranza è l'elemento che ricorre più della metà della dimensione dell'array . Ciò significa che l'elemento di maggioranza si verifica più di tutti gli altri elementi combinati o se contate il numero di volte, viene visualizzato l'elemento di maggioranza e sottraendo il numero di tutti gli altri elementi, otterrete un numero positivo.

Quindi, se conti il ??numero di alcuni elementi e sottrai il numero di tutti gli altri elementi e ottieni il numero 0 - il tuo elemento originale non può essere un elemento di maggioranza. Questo se la base per un algoritmo corretto:

Hanno due variabili, contatore e possibile elemento. Iterate il flusso, se il contatore è 0 - sovrascrivete il possibile elemento e inizializzate il contatore, se il numero è uguale al possibile elemento - aumentate il contatore, altrimenti diminuitelo. Codice Python:

def majority_element(arr):
    counter, possible_element = 0, None
    for i in arr:
        if counter == 0:
            possible_element, counter = i, 1
        elif i == possible_element:
            counter += 1
        else:
            counter -= 1

    return possible_element

È chiaro che l'algoritmo è O (n) con una costante molto piccola prima di O (n) (come 3). Inoltre sembra che la complessità dello spazio sia O (1) , perché abbiamo solo tre variabili inizializzate. Il problema è che una di queste variabili è un contatore che potenzialmente può crescere fino a n (quando l'array è costituito dagli stessi numeri). E per memorizzare il numero n è necessario lo spazio O (log (n)) . Quindi dal punto di vista teorico è O (n) time e O (log (n)) space. Da pratico , puoi inserire 2 ^ 128 numeri in un longint e questo numero di elementi nell'array è inimmaginabilmente enorme.

Si noti inoltre che l'algoritmo funziona solo se è presente un elemento di maggioranza. Se tale elemento non esiste restituirà comunque un numero, il che sarà sicuramente sbagliato. (è facile modificare l'algoritmo per dire se esiste l'elemento di maggioranza)

Canale storico: questo algoritmo è stato inventato da qualche parte nel 1982 da Boyer, Moore e chiamato Boyer & # 8211; algoritmo di voto a maggioranza Moore .

Answer 7

Ho ricordi di questo algoritmo, che potrebbe o meno seguire la regola 2K. Potrebbe essere necessario riscriverlo con pile e simili per evitare di rompere i limiti di memoria a causa delle chiamate di funzione, ma questo potrebbe non essere necessario poiché ha sempre e solo un numero logaritmico di tali chiamate. Ad ogni modo, ho vaghi ricordi del college o una soluzione ricorsiva a questo che comportava divisione e conquista, il segreto è che quando dividi i gruppi a metà, almeno una delle metà ha ancora più della metà dei suoi valori pari al massimo . La regola di base quando si divide è che tu restituisca due valori primi candidati, uno dei quali è il valore più alto e uno dei quali è un altro valore (che può essere o meno il 2 ° posto). Ho dimenticato l'algoritmo stesso.

Answer 8

Prova di correttezza per la risposta di buti-oxa / Jason Hernandez, supponendo che la risposta di Jason sia la stessa della risposta di buti-oxa ed entrambi funzionano nel modo in cui dovrebbe funzionare l'algoritmo descritto:

Definiamo la forza sospetta adattata come uguale alla forza sospetta se viene selezionato il valore massimo o -sospensione se il valore massimo non è selezionato. Ogni volta che scegli il numero giusto, la forza sospetta attualmente regolata aumenta di 1. Ogni volta che scegli un numero sbagliato, diminuisce di 1 o aumenta di 1, a seconda che sia selezionato il numero sbagliato. Pertanto, la forza minima di sospetto corretta per il finale possibile è uguale al numero di [valori massimi] - numero di [altri valori]