リスト内の重複のペアの数を返すアルゴリズムを見つけようとしています。効率的に重複のペアの数を見つける
例： 入力：[13,4,8,4,13,7,13,9,13] 出力：7 （4〜13の1対に出てくる6対および2つの4者に出てきます）
私のアルゴリズムはより効率的になりますか？ 〜ここ
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)
ここにはO（N）で動作するアルゴリズムがあります。
なぜO（N^2）でないのですか？あなたは、すべての要素をdictのために一度、そして計算のためにもう一度繰り返すと言っていますか？ –
@JamalCrawford .. Big O表記で定数値が無視されるため、何かを2度実行するとO（2N）になります。http://stackoverflow.com/questions/22188851/why-is-constant-always大きな分析から降した – samgak
参考になりました。それは物事をクリア！ –
はjavascriptのコードで、あなたは複雑さが線形である、phythonコードにこれを変換することができます：私は私が持っているものである（N^2）
ここで、それは速くシータよりになりたいです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);
@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
どのようにすることができます '4 13の6 pairs'、なぜ' 2 pairs'に出てきますか？ –
私は 'python'を知らないのですが、これは' java/php/js/perl/c/C++ ' –
と書くことができます。13は6種類のユニークなペアを作成します。 （13.1,13.2）（13.1,13.3）（13.1,13.4）（13.2,13.3）（13.2,13.4）（13.3,13.4） –