gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-12-03 16:29:59 31 4
gpt4 key购买 nike

我有两个排序的列表,例如

a = [1, 4, 7, 8]
b = [1, 2, 3, 4, 5, 6]
我想知道 a中的每个项目是否在 b中。对于上面的示例,我想找到
a_in_b = [True, True, False, False]
(或者也可以将 a_in_bTrue的索引也可以)。
现在, ab都非常大,因此复杂性成为一个问题。如果是 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为空)。

关于python - “输入”两个具有最低复杂度的排序列表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/65789112/

31 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com