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

Question

假设我有两个列表 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|)。这个对吗？

Answer 1

你应该使用 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}
...