gpt4 book ai didi

python - 我应该使用字典进行成员资格测试吗?

转载 作者:行者123 更新时间:2023-12-05 03:55:07 25 4
gpt4 key购买 nike

假设我有两个列表 A、B,这样 A 是 B 的子集。如果我要解析 B 的点,并且每次我想测试一个元素是否是 A 的成员,那么将 A 表示为字典比列表更好?我问是因为我的印象是字典的最坏情况查找时间为 O(1),而数组为 O(n)。

即以下哪项在时间复杂度方面效率更高?

# Code 1
A = [1, 2, 3]
B = [1, 2, 3, 4, 5, 6, 7, 8, 1, 2, 3, 4, 1, 2, 3]

for i in B:
if i in A:
print (i)
else:
print (-1)
# Code 2
A = [1, 2, 3]
B = [1, 2, 3, 4, 5, 6, 7, 8, 1, 2, 3, 4, 1, 2, 3]

A_dict = {}
for i in A:
A_dict[i] = 0

for i in B:
if i in A_dict:
print (i)
else:
print (-1)

看来,如果我上面所说的时间复杂度是正确的,那么第一个代码的复杂度为 O(|B| x |A|),而第二个代码的复杂度为 O(|B|)。这个对吗?

最佳答案

你应该使用 sets为了那个原因。它们具有 O(1) 查找,如字典,但它们不是键值对。

您的代码将如下所示:

A = [1, 2, 3]
B = [1, 2, 3, 4, 5, 6, 7, 8, 1, 2, 3, 4, 1, 2, 3]

A_set = set(A)

for i in B:
if i in A_set:
print (i)
else:
print (-1)

或:

A = {1, 2, 3}
...

关于python - 我应该使用字典进行成员资格测试吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/60447358/

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