在两个排序列表中查找匹配项的更好方法，而不是使用 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）。