forループを使用するよりも2つのソート済みリストで一致するものを見つける方が良いでしょうか？ （Java）

Question

私は2つのソートされたリストを両方とも降順で持っています。たとえば、要素が[2,3,4,5,6,7...]のソートされたリンクされたリストと、要素が[5,6,7,8,9...]のソート済みリストがあります。

両方のリストで共通の要素をすべて見つける必要があります。 forループと入れ子になったループを使ってすべての一致を繰り返して、同じ2つの要素を見つけることができます。しかし、実行時間がO(n^2)未満のこれを行う別の方法がありますか？

Answer 1

あなたはO（n）時にそれを行うことができます。擬似コード：

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

最初のリストをHashSetに変換します。各要素がHashSetにあるかどうかをチェックする第2のリストを反復する。

Answer 3

メインループでは、両方のリストから最初の要素を取り出して比較します。それらが等しくない場合は、他のループの要素と等しいかそれ以上になるまで、要素の少ないリストをスキャンします。等しい場合、これは共通の要素を見つけたことを意味します。共通要素が渡されるまで、両方のリストを順番に読みます。メインループを続行します。このアプローチの複雑さはO（n + m）です。

Answer 4

実際にあなたが少し良く行うことができます。

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)