什么是两个已排序列表相交的最快算法？

Question

假设有两个已排序的列表A和B。

A和B中的条目数可能会有所变化。(它们可以非常小/巨大。它们可以相似/显着不同)。

这种功能已知的最快算法是什么？

有没有人能给我一个想法或参考文献？

- syko

---

你可以通过在列表A中应用二分查找来执行O(nlog(n))，以查找列表B中的所有元素。如果列表的大小非常不同，则最好在较大的列表中进行搜索。 - Shubham

似乎你的方法不太好。为什么要问最快已知算法，而不是开发自己的算法，避免不必要的步骤呢？ - xenteros

@syko 我在下面给你提供了可用的代码。 - xenteros

请问您提到的“list”是指“链表（linked list）”吗？对于您的问题，答案部分取决于您的列表是否支持二分查找。 - John Coleman

@JohnColeman 你可以将其视为数组，而不是链表。因此，当然可以使用二分搜索。 - syko

Answer 1

假设 A 有 m 个元素，B 有 n 个元素，并且 m ≥ n。 从信息论的角度来看，我们能做到最好的是：

   (m + n)!
lg -------- = n lg (m/n) + O(n)
    m!  n!

由于要验证空交集，我们基本上必须执行排序合并，因此需要进行比较。通过遍历 B 并在 A 中保持“游标”以指示应插入的最近一个元素的位置来维护排序顺序。我们使用指数搜索来推进光标，总成本大致为：

lg x_1 + lg x_2 + ... + lg x_n,

其中x_1 + x_2 + ... + x_n = m + n是m的某个整数划分。由于lg的凹性，这个和是O(n lg (m/n))。

- David Eisenstat

---

谢谢！这是所描述算法的Python版本：https://gist.github.com/fjsj/9c9f7f36cfd3205343e333d86778433c看起来运行良好。 - fjsj

Answer 2

我不确定这是否是最快的选项，但以下是一种时间复杂度为O(n+m)的方法，其中n和m是您列表的大小：

• 循环遍历两个列表，直到其中一个为空，具体步骤如下：
• 在一个列表上前进一步。
• 在另一个列表上前进，直到找到一个值等于或大于另一个列表当前值的值。
• 如果相等，则该元素属于交集，可以将其附加到另一个列表中。
• 如果大于另一个元素，请在另一个列表上前进，直到找到一个等于或大于此值的值。
• 重复以上步骤，直到其中一个列表为空。

- Keiwan

---

这是对于链表而言很自然且可能是最优的（因为线性扫描是不可避免的）。另一方面，如果可以进行随机访问（例如Python中的列表，实际上是数组），则使用二分搜索来查找下一个公共元素可能会更好，尤其是在列表很大且交集很小的情况下。似乎不知道列表的一些详细信息很难确定最佳方法。 - John Coleman

@JohnColeman 没错。我的答案基于这样一个假设，即 OP 所说的链表不是在内部由数组支持的（例如 Java 的 ArrayList 或许多其他编程语言中的 Arrays/Lists），因此无法以 O(1) 访问元素。 - Keiwan

Answer 3

这里是一个简单且经过测试的Python实现，它使用二分搜索来推进两个列表的指针。
它假设输入的两个列表都已排序且不包含重复项。

import bisect

def compute_intersection_list(l1, l2):
    # A is the smaller list
    A, B = (l1, l2) if len(l1) < len(l2) else (l2, l1)
    i = 0
    j = 0
    intersection_list = []
    while i < len(A) and j < len(B):
        if A[i] == B[j]:
            intersection_list.append(A[i])
            i += 1
            j += 1
        elif A[i] < B[j]:
            i = bisect.bisect_left(A, B[j], lo=i+1)
        else:
            j = bisect.bisect_left(B, A[i], lo=j+1)
    return intersection_list


# test on many random cases
import random

MM = 100  # max value

for _ in range(10000):
    M1 = random.randint(0, MM)  # random max value
    N1 = random.randint(0, M1)  # random number of values
    M2 = random.randint(0, MM)  # random max value
    N2 = random.randint(0, M2)  # random number of values
    a = sorted(random.sample(range(M1), N1))  # sampling without replacement to have no duplicates
    b = sorted(random.sample(range(M2), N2))
    assert compute_intersection_list(a, b) == sorted(set(a).intersection(b))

- Ismael EL ATIFI