Un modo migliore per trovare corrispondenze in due elenchi ordinati rispetto all'utilizzo per i cicli? (Java)

Question

Ho due elenchi ordinati, entrambi in ordine decrescente. Ad esempio, ho una lista collegata ordinata con elementi [2,3,4,5,6,7...] e l'altra con elementi [5,6,7,8,9...].

Devo trovare tutti gli elementi comuni in entrambe le liste. So che posso usare un ciclo for e un ciclo annidato per iterare tutte le corrispondenze per trovare gli stessi due elementi. Tuttavia, c'è un altro modo per farlo che ha un tempo di esecuzione inferiore a O(n^2)?

Answer 1

È possibile farlo nel tempo O (n). Pseudocodice:

a = list1.first 
b = list2.first 
repeat: 
    if a == b: 
     output a 
     a = list1.next 
     b = list2.next 
    elif a < b: 
     a = list1.next 
    else 
     b = list2.next 
until either list has no more elements 

Answer 2

Convertire il primo elenco in un HashSet; quindi scorrere il secondo elenco controllando se ciascun elemento si trova nello HashSet.

Answer 3

Nel ciclo principale, prendere i primi elementi da entrambi gli elenchi e confrontare. Se non sono uguali, scansiona l'elenco con meno elementi finché non diventa uguale o superiore all'elemento dell'altro ciclo. Se diventa uguale, significa che hai trovato un elemento comune. Leggere entrambi gli elenchi in sequenza fino a quando non viene passato l'elemento comune. Continua il ciclo principale. La complessità di questo approccio è O (n + m).

Answer 4

In realtà si può fare un po 'meglio:

def dropWhile(ls, cond): 
    if cond(ls[0]): return dropWhile(ls[1:], cond) 
    return ls 

def bisect(ls, v): 
    """ 
    Finds largest i s.t. ls[i]<=v and returns it. 
    If no such i exists it returns -1. 
    Runs in O(log n) 
    """ 
    pass 

def find_commons(ls1, ls2, ret): 
    if not (ls1 or ls2): return 
    i = bisect(ls2, ls1[0]) 
    if i<0: find_commons(ls2, ls1[1:], ret) 
    elif ls2[i]==ls1[0]: 
     ret.append(ls1[0]) 
     trim = lambda ls: dropWhile(lambda x: x==ls1[0], ls) 
     find_commons(trim(ls1), trim(ls2), ret) 
    else: find_commons(ls2[i+1:], ls1, ret)