Algoritmo veloce per la ricerca di elementi comuni di due elenchi ordinati

Question

Algoritmo veloce per la ricerca di elementi comuni di due elenchi ordinati

#1 da (15 voti)
#2 da (4 voti)

7

Supponiamo di avere due liste di N 3 per 3 vettori di numeri interi.

Ho bisogno di trovare un modo rapido (ad esempio del tempo di esecuzione al massimo N ^ (1 + epsilon)) per trovare i vettori della prima lista che hanno la stessa prima coordinata con un vettore della seconda lista.

Naturalmente, potrei fare il seguente ingenuo copmarison:

for u in list_1 do
for v in list_2
if u[1] equals v[1] then
print u;print v;
end if;end for; end for;

Questo, tuttavia, richiederebbe N ^ 2 cicli.

Sento che ordinamento delle due liste in base alla loro prima coordinata e poi cercare le collisioni è forse un modo veloce. Bubbleshort, ecc., Probabilmente prenderebbe logN time, ma non riesco davvero a vedere come codificare la ricerca di collisione tra le liste ordinate.

Qualsiasi aiuto sarebbe apprezzato.

sorting pseudocode

posta manenir 01.06.2011 - 23:30

fonte

2 risposte

Leggi altre domande sui tag sorting pseudocode

Come convincere i collaboratori dei meriti degli ambienti di sviluppo locale Boss vuole convertire tutti gli sviluppatori in desktop virtualizzati [duplicati]

score 15 · Answer 1

Il modo ingenuo richiede O (N ^ 2) tempo, corretto. L'ordinamento degli elenchi richiede prima O (N log N) tempo, assumendo che si utilizzi un buon algoritmo (bubblesort è O (N ^ 2)) e il resto è O (N), quindi il tempo totale è O (N log N).

Se è possibile utilizzare una tabella hash che consente più voci (C ++ 0x std :: unordered_multimap sarebbe l'ideale) è possibile ottenere prestazioni normali fino a O (N). Basta inserire gli elementi di un vettore nella tabella hash, prima coordinare come chiave e l'intero vettore come valore, quindi passare attraverso l'altro vettore, cercando i primi valori delle coordinate.

score 4 · Answer 2

Ecco una risposta rapida e sporca di O(N) Python per te che usa solo gli elenchi dati. Funziona solo se entrambe le liste sono ORDINATE. Ho bisogno di pulire questo, ma illustra ciò che devi fare. Ho scelto i brutti nomi per le variabili; Lo pulirò più tardi.

def test():
    sorted_full = [1,3,5,7,9,11,15,17]
    sorted_sub = [5,11,17]

    full_ix = 0
    sub_ix = 0

    while full_ix < len(sorted_full) and sub_ix < len(sorted_sub):
        curr_full = sorted_full[full_ix]
        curr_sub = sorted_sub[sub_ix]
        if curr_full == curr_sub:
            print('Common id ' + str(curr_full) + ' at index ' + str(full_ix))
            full_ix +=1
            sub_ix +=1
            continue
        if curr_full < curr_sub:
            full_ix +=1
        else:
            sub_ix+=1


test()