python - “输入”两个具有最低复杂度的排序列表

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)低的复杂性？

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