'in' 表示两个复杂度最低的排序列表

我有两个sorted列表，例如

a = [1, 4, 7, 8]
b = [1, 2, 3, 4, 5, 6]

我想知道其中的每一项a如果它在b。对于上面的例子，我想找到

a_in_b = [True, True, False, False]

（或具有索引，其中a_in_b is True也会好的）。

现在，两者a and b非常大，因此复杂性是一个问题。如果M = len(a) and N = len(b). 我怎样才能以低于M * O(N)利用两个列表都已排序的事实？

您可以迭代您的b在循环内手动列出a。你会想要推进b当您从中看到的最新值小于当前值时进行迭代a.

from math import inf

result = []
b_iter = iter(b)                           # create an iterator over b
b_val = -inf
for a_val in a:
    while b_val < a_val:
        b_val = next(b_iter, inf)          # manually iterate on it
    result.append(a_val == b_val)

这应该有一个运行时间O(M+N)，因为每个列表项最多迭代一次（b甚至可能不需要完全迭代）。

如果您愿意，您可以避免使用浮点无穷大，但是您需要做一些额外的工作来处理一些边缘情况（例如，如果b是空的）。