python - 有效查找重复项对的数量

Question

我正在尝试找到一种返回列表中重复项对数量的算法。

示例: 输入:[13,4,8,4,13,7,13,9,13] 输出:7 (4 个 13 组成 6 对，两个 4 组成 1 对)

我的算法可以变得更高效吗？我希望它比 Theta(n^2) 更快

这是我所拥有的:

my_List=[13,3,8,3,13,7,13,9,13]

pairs=0
alreadySeen=[]

for element in my_List:
  howMany=0
  if element in alreadySeen:
    False
   else:
    howMany=my_List.count(element)
    pairs=pairs+((howMany*(howMany-1))/2)
    howMany=0
    alreadySeen.append(element)

print(pairs)

Answer 1

这是一个运行时间复杂度为 O(N) 的算法。

1. 迭代元素一次以创建每个元素及其计数的字典。 对于您的示例，此步骤的输出为 {13: 4, 4:2, 8:1, ...}
2. 迭代该字典并计算每个元素的对数。每个元素的对数可以被认为是从 N 个元素的列表中选择 2 个项目。这可以通过计算 combinations 来完成使用公式 (N * (N-1))/2 无需重复。因此，对于 4 个元素，有 (4 * 3)/2 = 6 对。