python - 检查两个列表在 Python 中是否至少有 2 个共同项目的最快方法？

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 的最终解决方案，但我仍然遇到 TLE!

ids[] 是一个包含列表的列表，例如:ids= [ ['1','2','3']] 。使用Dictionary会提高速度吗？

我在编辑时遇到了一些麻烦，因为这是我在 Stack Overflow 中的第一个问题。

我要解决的问题是: 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