O (n log n) in Javascript-Algorithmus

Question

folgende Funktion:

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; 
} 

die Anzahl der Paarelemente innerhalb einer Anordnung findet, die eine Summe von K. I s es O hat (n^2/2) Gibt es einen anderen Algorithmus, um das oben genannte mit O(nlogn) zu implementieren?

Answer 1

Ja die Lösung, die Sie gebucht haben, hat O(n^2) Komplexität wegen der zwei for-Schleifen. Sie können das Problem in O(n) tatsächlich lösen, indem Sie map verwenden, das nur ein assoziatives Array in JavaScript ist.

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; 
    } 
} 

Answer 2

Wenn Sie Paare von Elementen zu finden, die Summe K in O (n log n) haben Sie sollten ein neues Array erstellen, in dem Sie eine sortierte Version des Array speichern, die als Parameter übergeben wurde, dann wie folgt vorgehen:

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; 
} 

Nun wird die Sortier- O (n log n) und der obige Code O (n), die es O (n log n) macht nimmt.