有效地找到重复对的数量

Question

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

示例：输入：[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

这里有一个javascript代码，你可以把它转成python代码，复杂度是线性的~O(n)

var arr = [13,3,8,3,13,7,13,9,13];
var count = {};
var totalpairs =0;
for(var i=0;i<arr.length;i++){
  if(count[arr[i]]){
    count[arr[i]]++;
  }else{
    count[arr[i]] =1;
  }
}

for(key in count){
  if(count[key] %2 == 0){
    totalpairs = totalpairs + count[key]/2;
  }
}

console.log(' total pairs are '+ totalpairs);

Answer 2

这是一个在 O(N) 中运行的算法。

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

Answer 3

@Hesham Attia 已经提供了正确的算法，这里是 Counter:

的简单实现

>>> from collections import Counter
>>> l = [13,4,8,4,13,7,13,9,13]
>>> sum(x * (x - 1) // 2 for x in Counter(l).values())
7

Answer 4

这是一种在时间复杂度为 ~ O(N) 的列表中查找所有可能的重复对的简单而有效的方法。

l = [13,3,8,3,13,7,13,9,13]
# Two pairs of 13 and One pair of 3
# Sum equals to Three
alreadySeen = []
total_no_of_pairs = 0
for i in range(len(l)):
    if l[i] not in alreadySeen:
        alreadySeen.append(l[i])
    else:
        # If element l[i] is present in alreadySeen list
        # Indicates a Pair and increments count
        # Remove element for creating a new pair
        total_no_of_pairs +=1
        alreadySeen.remove(l[i])

print(total_no_of_pairs)

输出：

Answer 5

时间复杂度：O(N)

arr = list(map(int,input().split()))
    d = {}
    for i in range(len(arr)):
        if arr[i] in d.keys():
            d[arr[i]] += 1
        else:
            d[arr[i]] = 1
    ans = 0
    for val in d.values():
        if val > 1:
            ans += val*(val-1)//2
    print(ans)

有效地找到重复对的数量

Efficiently find number of pairs of duplicates

python

iteration

algorithm

performance

big-o