Lepszy sposób wyszukiwania dopasowań na dwóch uporządkowanych listach niż w przypadku pętli? (Java)

Question

Mam dwie posortowane listy, obie w porządku malejącym. Na przykład mam jedną sortowaną połączoną listę z elementami [2,3,4,5,6,7...], a drugą z elementami [5,6,7,8,9...].

Potrzebuję znaleźć wszystkie typowe elementy na obu listach. Wiem, że mogę użyć pętli for i pętli zagnieżdżonej do iterowania wszystkich dopasowań, aby znaleźć te same dwa elementy. Czy jest jednak inny sposób wykonania tej czynności, który ma mniej niż O(n^2)?

Answer 1

Możesz to zrobić w O (n) czasie. Pseudokod:

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

Konwertuj pierwszą listę na HashSet; następnie przejrzyj drugą listę, sprawdzając, czy każdy element znajduje się w HashSet.

Answer 3

W głównej pętli, weź pierwsze elementy z obu list i porównaj. Jeśli nie są równe, zeskanuj listę mniejszą ilością, aż stanie się równa lub większa niż element drugiej pętli. Jeśli jest równa, oznacza to, że znalazłeś wspólny element. Odczytaj obie listy kolejno, aż wspólny element zostanie przekazany. Kontynuuj główną pętlę. Złożoność tego podejścia to O (n + m).

Answer 4

Właściwie można zrobić trochę lepiej:

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)