python - 'in' 用于具有最低复杂度的两个排序列表

Question

我有两个排序列表，例如

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

我想知道每个项目a是否在b. 对于上面的例子，我想找到

a_in_b = [True, True, False, False]

（或者有索引a_in_b也True可以）。

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

标签： python

Answer 1

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为空）。