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

html5 • • 问答

我有两个排序列表，例如

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

回答

您可以在循环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为空）。

回答

利用 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)。

  • It's not a red herring; the solution which exploits sortedness has the same time complexity, but uses O(1) auxiliary space compared to O(m) auxiliary space for the set-based solution.
以上是'in'表示复杂度最低的两个排序列表的全部内容。
THE END
分享
二维码
< <上一篇
下一篇>>