'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)利用两个列表都已排序的事实更低的复杂性来做到这一点？

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

Answer 2

利用 sorted'ness 是时间复杂度的一个红鲱鱼：理想的情况是在 O(n+m) 复杂度的锁步中迭代两者。这与转换b为 O(m) 的集合，然后在a集合中搜索 O(n)的元素相同。

>>> a = [1, 4, 7, 8]
>>> b = [1, 2, 3, 4, 5, 6]
>>> bs = set(b)                 # create set for O(len(b))
>>> [item in bs for item in a]  # check O(len(a)) items "in set of b" for O(1) each
[True, True, False, False]

由于大多数这些操作是内置的，唯一昂贵的操作是a所有解决方案都需要的迭代。

但是，这将复制对 中项目的引用b。如果b被视为算法的外部，则空间复杂度为 O(m+n) 而不是仅针对答案的理想情况 O(n)。

Answer 3

在这里使用二分搜索：

def bs(b,aele,start,end):
    if start > end:
        return False
    mid = (start + end) // 2
    if ale == b[mid]:
        return True

    if ale < b[mid]:
        return bs(b, aele, start, mid-1)
    else:
        return bs(b, aele, mid+1, end)

对于 a 中的每个元素，使用此方法检查它是否存在于b中。时间复杂度：O(m*log(n))