在Python中检查两个列表是否至少有两个公共项的最快方法是什么？

Question

 a={}

 t= list(map(int,input().split()))
 n=t[0]
 k=t[1]

 for i in range(n):
    a.update({i:[]})

 ids=[] 

 for i in range(n):
     k=input().split()
     ids.append(set(k[1:]))


 def ifrel(i, j):
    if i==j:
      return False
    return len(ids[i] & ids[j]) >= 2

 for i in range(n):
    for j in range(n):
       if ifrel(i,j):
          a[i].append(j)
 stack=[]
 res=[]
 def iterdfs(g,s):
     stack.append(s)
     while stack!=[]:
       k=stack.pop()
       if k not in res:
          res.append(k)
       for i in g[k]:
          if i not in res: 
         stack.append(i)
     return res

  print(len(iterdfs(a,0)))

这里是使用Set的最终解决方案，但我还是得到了一些帮助！你知道吗

ids[]是一个包含列表的列表，例如：ids=[['1'，'2'，'3']]。使用字典能提高速度吗？你知道吗

由于这是我在堆栈溢出中的第一个问题，所以我对编辑有些不安。你知道吗

我想解决的问题是： https://www.codechef.com/IOIPRAC/problems/INOI1302/

Answer 1

如果你想要最快的解决方案，它就不会很简洁。这里的尝试是最坏情况O（A+B），但是一旦找到两个匹配项就会退出，并且是最佳情况Ω（B），其中B是两个列表中的较短者。你知道吗

def check_common_items(A, B, n=2):

    # set B to be the shorter list, len is O(1)
    if len(B) < len(A):
        A, B = B, A

    B_set = set(B) # O(len(B))

    count = 0
    for a in A: # worst case O(len(A))
        if a in B_set: # O(1)
            count += 1
            if count == n:
                return True
    return False

然而，大多数使用集合的实现将是渐近有效的。例如，下面的函数可能不会太慢。你知道吗

def check_common_items(A, B, n=2):
    return len(set(A) & set(B)) >= n

Answer 2

您需要想出一个更有效的算法，而不是对照两个列表的全部内容进行检查，您可以在识别出两个重复项后终止：

a = ['some', 'list']
b = ['some', 'other', 'list']
duplicate_count = 0
my_bool = False
for item in a:
    if item in b:
        duplicate_count += 1
    if duplicate_count >= 2:
        my_bool = True
        break

该算法在最坏情况下仍为O（n²），但有提前终止的可能

Answer 3

使用一套。你知道吗

In [1]: lst1 = [1, 2, 3, 4]
In [2]: lst2 = [3, 4, 5, 6]
In [3]: set(lst1).intersection(set(lst2))
Out[3]: {3, 4}
In [4]: len(set(lst1).intersection(set(lst2)))
Out[4]: 2