Programme JavaScript pour imprimer tous les triplets formant AP dans un tableau trié

AP est une suite arithmétique où la différence entre deux éléments consécutifs est toujours la même. Nous imprimerons tous les triplets du tableau trié qui forment l'AP en utilisant trois méthodes : la méthode naïve, la méthode de recherche binaire et la méthode à deux pointeurs.

Introduction au problème

Dans cette question, nous obtenons un tableau trié, ce qui signifie que tous les éléments sont sous forme croissante. Nous devons trouver trois éléments dans le tableau et former un AP. Par exemple -

Tableau donné : 1 5 2 4 3

À partir du tableau donné, nous avons deux triples : 1 2 3 et 5 4 3 puisque la différence entre les éléments adjacents est égale. De plus, comme écrit, nous n'avons besoin que de trouver des triplets, nous ne trouvons donc pas de séquences plus longues.

Passons aux méthodes de recherche de triplets -

Méthode

Méthode naïve

Dans cette méthode, nous nous déplaçons simplement sur le tableau à l'aide d'une boucle et pour chaque itération, nous parcourrons un autre tableau pour un nombre plus grand que l'index actuel. Ensuite, nous implémenterons à nouveau un tableau imbriqué dans le premier tableau imbriqué pour trouver les éléments pouvant former AP. Regardons le code -

Exemple

// 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)

La complexité temporelle du code ci-dessus est O(), où N est la taille du tableau.

La complexité spatiale du code ci-dessus est O(1) car nous n'utilisons aucun espace supplémentaire.

Suivez la méthode simple

Dans la méthode précédente, lorsque nous avons deux éléments, nous pouvons trouver le troisième élément car nous avons des différences communes, donc pour trouver le troisième élément, au lieu d'utiliser la recherche linéaire, nous pouvons utiliser la recherche binaire et réduire la complexité temporelle du code ci-dessus -

Exemple

// 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)

La complexité temporelle du code ci-dessus est O(), où N est la taille du tableau.

La complexité spatiale du code ci-dessus est O(1) car nous n'utilisons aucun espace supplémentaire.

Méthode efficace

Dans cette méthode, nous utiliserons deux pointeurs et trouverons l'élément qui a la même différence que la position actuelle. Regardons le code -

Exemple

// 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)

La complexité temporelle du code ci-dessus est O(N*N), où N est la taille du tableau donné, et la complexité spatiale de la méthode ci-dessus est O(1) car nous n'utilisons aucun espace supplémentaire. p>

Remarque - Les deux premières méthodes sont valables pour tout type de tableau trié ou non, mais la dernière méthode est uniquement pour les tableaux triés, si le tableau n'est pas trié, nous pouvons le trier, mais cette méthode est toujours la meilleure parmi toutes autres.

Conclusion

Dans ce tutoriel, nous avons implémenté un programme JavaScript pour imprimer tous les triplets formant AP dans un tableau trié donné. Ap est une progression arithmétique dans laquelle la différence entre deux éléments consécutifs est toujours la même. Nous avons vu trois méthodes : la méthode naïve avec une complexité temporelle O(N*N*N), la méthode de recherche binaire avec une complexité temporelle O(N*N*log(N)) et la méthode à deux pointeurs.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!