java - 在两个排序列表中查找匹配项比使用 for 循环更好的方法？

Question

我有两个排序列表，都是非递减顺序。例如，我有一个带元素的排序链表，[2,3,4,5,6,7...]另一个带元素的链表[5,6,7,8,9...]。

我需要在两个列表中找到所有常见元素。我知道我可以使用 for 循环和嵌套循环来迭代所有匹配项以找到相同的两个元素。但是，是否有另一种运行时间小于 的方法来做到这一点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

其实你可以做得更好一点：

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)

Answer 3

将第一个列表转换为HashSet; 然后遍历第二个列表，检查每个元素是否在HashSet.

Answer 4

在主循环中，从两个列表中获取第一个元素并进行比较。如果它们不相等，则扫描具有较少元素的列表，直到它等于或大于另一个循环的元素。如果它相等，这意味着你找到了一个共同的元素。依次读取两个列表，直到通过公共元素。继续主循环。这种方法的复杂度是 O(n+m)。