İki sıralanmış listelerindeki eşleşmeleri döngüler için kullanmanın daha iyi bir yolu? (Java)

Question

Her ikisi de azalan sırada olmayan iki tane sıralı listelerim var. Örneğin, [2,3,4,5,6,7...] öğelerini ve diğeri [5,6,7,8,9...] öğelerini içeren bir sıralanmış bir listeye sahibim.

Her iki listede de tüm ortak öğeleri bulmam gerekiyor. Aynı iki öğeyi bulmak için tüm eşleşmeleri yinelemek için bir döngü ve yuvalanmış bir döngü kullanabileceğimi biliyorum. Ancak, O(n^2)'dan daha az çalışma süresi olan bunu yapmanın başka bir yolu var mı?

Answer 1

O (n) saatinde yapabilirsiniz. Sözdizimi kodu:

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

İlk listeyi HashSet; sonra her öğenin HashSet içinde olup olmadığını kontrol ederek ikinci listeden yineleyin.

Answer 3

Ana döngüde, her iki listeden de ilk öğeleri alın ve karşılaştırın. Eşit değilse, listeyi diğer döngü öğesinden eşit veya daha fazla olana dek daha az elemanla tarayın. Eşit ise, bu ortak bir unsur bulduğunuz anlamına gelir. Ortak öğe geçene kadar her iki listeyi de sırayla okuyun. Ana döngüye devam edin. Bu yaklaşımın karmaşıklığı O (n + m) 'dir.

Answer 4

Aslında biraz daha iyi yapabilirsiniz:

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)