次の関数：JavascriptのアルゴリズムでO（nlogn）
function solution(K, A) {
var counter=0;
for (var i=0;i<A.length;i++) {
for (var j=i;j<A.length;j++) {
if (A[i]+A[j]===K) {
if (i===j)
counter++;
else
counter+=2;
}
}
}
return counter;
}
がK. I の和を有するアレイ内のペア要素の数は、それはO（N^2/2 S認めます）？O(nlogn)で上記を実装する別のアルゴリズムがありますか？
はいループ用の2つの理由で、投稿したソリューションの複雑さはO(n^2)です。実際にO(n)の問題を解決するには、JavaScriptの連想配列であるmapを使用します。
function solution(k, arr){
var map = {};
for (var i=0; i < arr.length ; i++){
var tmp = k - arr[i];
if (temp > 0 && map[tmp] == 1)
console.log("Found the pair :", temp, arr[i]);
else
map[arr[i]] = 1;
}
}
'map'はおそらく配列ではなくオブジェクトでなければなりません。 –
アソシエート配列は実際にはJavaScriptのオブジェクトです –
上記のコードが正しく動作すると言いたいのですか？ –
あなたは合計OでK（nlog n）を持つ要素のペアを見つけたい場合は、あなたがして、パラメータとして渡された配列のソートされたバージョンを保存する新しい配列を作成する必要があります
var i = 0;
var j = A.length - 1;
while(i < j) {
if(A[i] + A[j] == k) {
counter++;
++i;
--j;
}
else
if(A[i] + A[j] < k) {
++i;
}
else
++j;
}
今選別は、O（nlogn）せるO（nlogn）上記コードO（N）を取る：次の操作を行います。
なぜi == jでカウンタがインクリメントされるのですか？同じインデックスの場合は、おそらくペアではありません。 – Nomaed
実際には、ルックアップテーブルを使ってO（n）でこの問題を解決して解決することができます。これは標準的なインタビューの質問です。 –
はい、それはn^2です。配列が順序付けられていない場合、私はあなたがそれより優れているとは思えません。 – nurdyguy