JavaScript-Programm zum Drucken aller AP-bildenden Tripel in einem sortierten Array

AP ist eine arithmetische Folge, bei der die Differenz zwischen zwei aufeinanderfolgenden Elementen immer gleich ist. Wir werden alle Tripel im sortierten Array, die den AP bilden, mit drei Methoden drucken: der naiven Methode, der binären Suchmethode und der Zwei-Zeiger-Methode.

Einführung in das Problem

In dieser Frage erhalten wir ein sortiertes Array, was bedeutet, dass alle Elemente in aufsteigender Form vorliegen. Wir müssen drei Elemente im Array finden und einen AP bilden. Zum Beispiel -

Gegebenes Array: 1 5 2 4 3

Aus dem gegebenen Array haben wir zwei Tripel: 1 2 3 und 5 4 3, da die Differenz zwischen benachbarten Elementen gleich ist. Außerdem müssen wir, wie geschrieben, nur Tripel finden, sodass wir keine längeren Folgen finden.

Wenden wir uns den Methoden zum Finden von Tripeln zu -

Methode

Naive Methode

Bei dieser Methode bewegen wir uns einfach mit einer Schleife über das Array und durchlaufen bei jeder Iteration ein anderes Array für eine größere Zahl im Vergleich zum aktuellen Index. Anschließend implementieren wir erneut ein verschachteltes Array innerhalb des ersten verschachtelten Arrays, um die Elemente zu finden, die AP bilden können. Schauen wir uns den Code an -

Beispiel

// function to find all the triplets 
function findAP(arr){
   var n = arr.length
   // traversing over the array
   for(var i = 0; i< n;i++){
      for(var j = i+1;j<n;j++){
         for(var k = j+1; k < n; k++){
            if(arr[j] - arr[i] == arr[k] - arr[j]) {
               console.log("Triplet is: " + arr[i] + " " + arr[j] + " " + arr[k]);
            }
         }
      }
   }
}
// defining the array and calling the function 
arr = [1, 5, 2, 4, 3]
findAP(arr)

Die zeitliche Komplexität des obigen Codes beträgt O(), wobei N die Größe des Arrays ist.

Die Speicherplatzkomplexität des obigen Codes beträgt O(1), da wir keinen zusätzlichen Speicherplatz verwenden.

Folgen Sie der einfachen Methode

Wenn wir in der vorherigen Methode zwei Elemente haben, können wir das dritte Element finden, da wir gemeinsame Unterschiede haben. Um das dritte Element zu finden, können wir anstelle der linearen Suche die binäre Suche verwenden und die Zeitkomplexität des obigen Codes reduzieren -

Beispiel

// function for binary search 
var binarySearch = function (arr, x, start, end) {
   if (start > end) return false;
   var mid=Math.floor((start + end)/2);
   if (arr[mid]===x) return true;
   if(arr[mid] > x)
      return binarySearch(arr, x, start, mid-1);
   else
      return binarySearch(arr, x, mid+1, end);
}
// function to find all the tripletes 
function findAP(arr){
   var n = arr.length
   // traversing over the array
   for(var i = 0; i< n;i++){
      for(var j = i+1;j<n;j++){
         // third element will be
         var third = 2*arr[j]-arr[i];
         if(binarySearch(arr,third,j+1,n)){
            console.log("Triplet is: " + arr[i] + " " + arr[j] + " " + third);
         }
      }
   }
}
// defining the array and calling the function 
arr = [1, 5, 2, 4, 3]
findAP(arr)

Die zeitliche Komplexität des obigen Codes beträgt O(), wobei N die Größe des Arrays ist.

Die Speicherplatzkomplexität des obigen Codes beträgt O(1), da wir keinen zusätzlichen Speicherplatz verwenden.

Effiziente Methode

Bei dieser Methode verwenden wir zwei Zeiger und finden das Element, das den gleichen Unterschied wie die aktuelle Position aufweist. Schauen wir uns den Code an -

Beispiel

// function to find all the triplets 
function findAP(arr){
   var n = arr.length
   
   // traversing over the array
   for(var i = 1; i< n;i++)    {
      var bptr = i-1
      var fptr = i+1
      while(bptr >= 0 && fptr < n)        {
         if(arr[i] - arr[bptr] == arr[fptr] - arr[i]){
            console.log("Triplet is: " + arr[bptr] + " " + arr[i] + " " + arr[fptr]);
            bptr--;
            fptr++;
         }
         else if(arr[i] - arr[bptr] > arr[fptr] - arr[i]){
            fptr++;
         }
         else{
            bptr--;
         }
      }
   }
}

// defining the array and calling the function 
arr = [1, 4, 7, 10, 13, 16]
findAP(arr)

Die zeitliche Komplexität des obigen Codes beträgt O(N*N), wobei N die Größe des angegebenen Arrays ist und die räumliche Komplexität der obigen Methode O(1) beträgt, da wir keinen zusätzlichen Speicherplatz verwenden. p>

HINWEIS – Die ersten beiden Methoden gelten für jede Art von sortiertem oder unsortiertem Array, aber die letzte Methode gilt nur für sortierte Arrays. Wenn das Array unsortiert ist, können wir es sortieren, aber diese Methode ist immer noch die beste unter allen andere.

Fazit

In diesem Tutorial haben wir ein JavaScript-Programm implementiert, um alle Tripel, die AP bilden, in einem bestimmten sortierten Array auszugeben. Ap ist eine arithmetische Folge, bei der die Differenz zwischen zwei aufeinanderfolgenden Elementen immer gleich ist. Wir haben drei Methoden gesehen: die naive Methode mit der Zeitkomplexität O(N*N*N), die binäre Suchmethode mit der Zeitkomplexität O(N*N*log(N)) und die Zwei-Zeiger-Methode.

Das obige ist der detaillierte Inhalt vonJavaScript-Programm zum Drucken aller AP-bildenden Tripel in einem sortierten Array. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!