trovare l'elemento verificano volte b in una matrice di dimensione n * k + b

Question

Descrizione

Dato un array di dimensioni (n*k+b) dove n elementi avvengono k volte e un elemento di verifica volte b, in altre parole non sono n+1 Elementi distinti. Dato che 0 < b < k trova l'elemento che si verifica b volte.

mie soluzioni tentate

1. soluzione ovvia useranno l'hashing, ma non funzionerà se i numeri sono molto grandi. La complessità è O(n)

2. usando la mappa per memorizzare le frequenze di ogni elemento e poi attraversare mappa per trovare l'elemento che si verificano b times.As Map sono implementate come altezza equilibrato alberi Complessità sarà O(nlogn).

Entrambi mia soluzione sono stati accettati, ma l'intervistatore ha voluto una soluzione lineare senza l'utilizzo di hashing e suggerimento ha dato era rendere l'altezza costante albero in albero in cui si archiviano le frequenze, ma io non sono in grado di capire ancora la soluzione corretta.

Voglio sapere come risolvere questo problema in tempo lineare senza hashing?

EDIT:

Esempio:

ingresso: n=2 b=2 k=3

Aarray: 2 2 2 3 3 3 1 1

uscita: 1

Answer 1

An idea usando gruppi ciclici

Per indovinare un bit di risposta, seguire questa procedura:

1. conte quanti numeri nella matrice ha i-esimo bit impostato, deposito come cnt
2. Se cnt % k è diverso da zero, allora i-esimo bit di risposta è impostata. Altrimenti è chiaro.

Per indovinare il numero intero, ripetere quanto sopra per ogni bit.

Questa soluzione è tecnicamente O((n*k+b)*log max N), dove max N è il valore massimo nella tabella, ma poiché il numero di bit è in genere costante, questa soluzione è lineare nella dimensione dell'array.

Nessun hashing, l'utilizzo della memoria è O(log k * log max N).

implementazione Esempio:

from random import randint, shuffle 

def generate_test_data(n, k, b): 
    k_rep = [randint(0, 1000) for i in xrange(n)] 
    b_rep = [randint(0, 1000)] 
    numbers = k_rep*k + b_rep*b 
    shuffle(numbers) 
    print "k_rep: ", k_rep 
    print "b_rep: ", b_rep 
    return numbers 

def solve(data, k): 
    cnts = [0]*10 
    for number in data: 
     bits = [number >> b & 1 for b in xrange(10)] 
     cnts = [cnts[i] + bits[i] for i in xrange(10)] 
    return reduce(lambda a,b:2*a+(b%k>0), reversed(cnts), 0) 

print "Answer: ", solve(generate_test_data(10, 15, 13), 3) 

Answer 2

Per avere un'altezza costante B-tree contenenti n elementi distinti, con altezza costante h, sono necessari z=n^(1/h) figli per i nodi: h=log_z(n), quindi h=log(n)/log(z), quindi log(z)=log(n)/h, quindi z=e^(log(n)/h), quindi z=n^(1/h).

Esempio, con n=1000000, h=10, z=3.98, ovvero z=4.

Il tempo per raggiungere un nodo in questo caso è O(h.log(z)). Supponendo h e z di essere "costante" (dal N=n.k, allora log(z)=log(n^(1/h))=log(N/k^(1/h))=ct scegliendo correttamente h sulla base di k, si può quindi dire che O(h.log(z))=O(1) ... Questo è un po 'inverosimile, ma forse era il tipo di cosa l'intervistatore ? voleva sentire

Answer 3

assumo:

1. gli elementi dell'array sono paragonabili
2. conosciamo i valori di n, k preventivamente
3. Una soluzione O (n * k + b..) è goo abbastanza

Lascia che il numero che si verifica solo b volte sia S. Stiamo cercando di trovare la S in un array di dimensioni n * k + b.

Passaggio ricorsivo: Trova l'elemento mediano della sezione di matrice corrente come in Ordinamento veloce nel tempo dell'ornamento. Lascia che l'elemento mediano sia M.

Dopo il passaggio ricorsivo si ha un array in cui tutti gli elementi più piccoli di M si verificano a sinistra della prima occorrenza di M. Tutti gli elementi M sono uno accanto all'altro e tutti gli elementi più grandi di M sono a destra di tutte le occorrenze di M.

Guardare l'indice della M più a sinistra e calcolare se S < M o S > = M. Recurse o sulla fetta sinistra o sulla fetta destra.

Così si sta facendo un ordinamento rapido, ma scavando solo una parte delle divisioni in qualsiasi momento. Riceverete O (logN) volte ma ogni volta con 1/2, 1/4, 1/8, .. dimensioni dell'array originale, quindi il tempo totale sarà ancora O (n).

Chiarificazione: Diciamo n = 20 ek = 10. Quindi, ci sono 21 elementi distinti nella matrice, 20 delle quali si verificano 10 volte e l'ultimo verificano diciamo 7 volte. Trovo l'elemento medio, diciamo che è 1111. Se S < 1111 dell'indice dell'occorrenza più a sinistra di 1111 sarà inferiore a 11 * 10. Se S> = 1111, l'indice sarà uguale a 11 * 10.

Esempio completo: n = 4. k = 3. Array = {} 1,2,3,4,5,1,2,3,4,5,1,2,3,5 Dopo il primo passo ricorsivo trovo che l'elemento mediano è 3 e l'array è qualcosa del tipo: {1,2,1,2,1,2,3,3,3,5,4,5,5,4} Ci sono 6 gli elementi a sinistra di 3. 6 è un multiplo di k = 3. Quindi ogni elemento deve essere presente 3 volte lì. Quindi S> = 3. Recurse sul lato destro. E così via.

Answer 4

UPDATE: questo uso hashing, quindi non è una buona risposta :(

in Python questo sarebbe tempo lineare (set rimuoverà i duplicati):

result = (sum(set(arr))*k - sum(arr))/(k - b) 

Answer 5

Se 'k' è pari e 'b' è dispari, allora XOR farà. :)