java - for ループを使用するよりも、2 つの並べ替えられたリストで一致を見つけるためのより良い方法は?

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

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

Answer 3

HashSet最初のリストを;に変換します。次に、各要素が にあるかどうかをチェックする 2 番目のリストを繰り返しHashSetます。