recherche

Maison  >  Article  >  interface Web  >  Programme JavaScript pour calculer l'inversion de taille 3 dans un tableau donné

Programme JavaScript pour calculer l'inversion de taille 3 dans un tableau donné

WBOY
WBOYavant
2023-09-08 11:33:021176parcourir

JavaScript 程序计算给定数组中大小为 3 的反转

Dans ce tutoriel, nous allons apprendre à calculer l'inversion de taille 3 dans un tableau donné.

Énoncé du problème - On nous donne un tableau de longueur n contenant différentes entrées numériques. Nous devons trouver le nombre total de paires de nombres de taille 3 tels que arr[i] > arr[j] > arr[k], où I

Ici, nous apprendrons d'abord la méthode de la force brute puis nous optimiserons sa complexité temporelle et spatiale.

Utilisez des méthodes de force brute

Dans l'approche par force brute, nous utiliserons trois boucles for imbriquées pour trouver des inversions de nombre de taille 3. La première boucle parcourt de 1 à n-2 éléments et la deuxième boucle parcourt du i-ème élément au n-1-ème élément. Si l'élément précédent est supérieur à l'élément suivant, parcourez le tableau et recherchez l'élément plus petit que l'élément du milieu.

Grammaire

Les utilisateurs peuvent utiliser la méthode de force brute selon la syntaxe ci-dessous pour calculer l'inversion de taille 3 dans un tableau donné. 

for ( ) {
   for ( ) {
      if (array[m] > array[n]) {
         for (let o = n + 1; o < len; o++) {
            if (array[n] > array[o])
            cnt++;
         }
      }
   }
}

Algorithme

  • Étape 1 - Parcourez les n-2 premiers éléments à l'aide d'une boucle for.

  • Étape 2 - Parcourez les éléments m+1 vers len-1 en utilisant une boucle for imbriquée.

  • Étape 3 - Dans la boucle for imbriquée, vérifiez si array[m] est supérieur à array[n]. Si tel est le cas, parcourez du n+1ème élément au dernier élément.

  • Étape 4 - Si l'élément au othième index est inférieur à l'élément au nième index, nous pouvons dire que nous avons trouvé une paire inversée valide de taille 3 et incrémenter la variable 'cnt' moins 1.

  • Étape 5 - Une fois toutes les itérations de la boucle for terminées, renvoyez la valeur de "cnt".

Exemple 1

Dans l'exemple ci-dessous, nous implémentons une méthode de force brute pour trouver le nombre total de paires d'inversion de taille 3.

Dans le tableau donné, l'utilisateur ne peut observer que 2 paires d'inversion dans la sortie. La première paire d'inversions est (10,5,4) et la deuxième paire d'inversions est (20,5,4). 

<html>
<body>
   <h3> Using the <i> Brute force approach </i> to Count Inversions of size three in a given array </h3>
   <div id = "output"> </div>
   <script>
      let output = document.getElementById('output');
      function InversionCount(array) {
         let len = array.length;
         let cnt = 0;
         for (let m = 0; m < len - 2; m++) {
            for (let n = m + 1; n < len - 1; n++) {
            if (array[m] > array[n]) {
                  for (let o = n + 1; o < len; o++) {
                     if (array[n] > array[o])
                     cnt++;
                  }
               }
            }
         }
         return cnt;
      }
      let array = [10, 20, 5, 4, 50, 60, 30, 40];
      output.innerHTML += "The count of inversion in the " + array + " is  " + InversionCount(array)
   </script>
</body>
</html>

Complexité temporelle et spatiale

  • Complexité temporelle - Puisque nous utilisons trois boucles for imbriquées, la complexité temporelle est O(n^3).

  • Complexité spatiale - Lorsque nous utilisons un espace constant, la complexité spatiale est O(1).

Utilisez deux boucles for imbriquées

Dans cette méthode, nous utiliserons deux boucles imbriquées. Nous retrouverons le nombre total d’éléments plus petits à droite de l’élément courant, et le nombre total d’éléments plus grands à gauche. Après cela, nous multiplions les deux pour obtenir le nombre total d’inversions pour un nombre spécifique.

Grammaire

Les utilisateurs peuvent suivre la syntaxe ci-dessous pour calculer des inversions de taille 3 en JavaScript à l'aide de deux boucles imbriquées. 

for ( ) {  
   // find a smaller element on the right  
   for ()
   if (array[m] < array[n])
   right++;
   
   // find bigger elements on the left
   for ()
   if (array[m] > array[n])
   left++;        
   cnt += right * left;
}

Algorithme

  • Étape 1 - Parcourez n éléments du tableau à l'aide d'une boucle for.

  • Étape 2 - Utilisez une boucle for pour rechercher tous les éléments à droite de l'élément actuel qui sont plus petits que l'élément actuel.

  • Étape 3 - Utilisez à nouveau la boucle for pour rechercher tous les éléments à gauche de l'élément actuel qui sont plus grands que l'élément actuel.

  • Étape 4 - Multipliez les valeurs des variables gauche et droite et ajoutez-les à la variable "cnt".

Exemple 2

Dans l'exemple ci-dessous, nous utilisons deux boucles imbriquées pour trouver le nombre total d'inversions de taille 3 comme indiqué dans la méthode ci-dessus. L'utilisateur peut constater que le résultat est le même que dans la première méthode. 

<html>
<body>
   <h3> Using the <i> two nested loops </i> to Count Inversions of size three in a given array </h3>
   <div id = "output"> </div>
   <script>
      let output = document.getElementById('output');
      function InversionCount(array) {
         let cnt = 0;
         let len = array.length;
         
         // Iterate through every element of the array
         for (let m = 0; m < len - 1; m++) {
         
            // count all element that are smaller than arr[m] and at the right to it
            let right = 0;
            for (let n = m - 1; n >= 0; n--)
            if (array[m] < array[n])
            right++;
            
            // count all element that are greater than arr[m] and at the left to it
            let left = 0;
            for (let n = m + 1; n < len; n++)
            if (array[m] > array[n])
            left++;
            
            // multiply left greater and right smaller elements
            cnt += right * left;
         }
         return cnt;
      }
      let array = [10, 20, 5, 4, 50, 60, 30, 40];
      output.innerHTML += "The count of inversion in the " + array + " is  " + InversionCount(array)
   </script>
</body>
</html>

Complexité temporelle et spatiale

  • Complexité temporelle - Puisque nous utilisons deux boucles imbriquées, la complexité temporelle de la méthode ci-dessus est O(n^2).

  • Complexité spatiale - Lorsque nous utilisons un espace constant, la complexité spatiale est O(1).

L'utilisateur a appris deux méthodes pour trouver des inversions de nombre de taille 3 dans un tableau donné. Dans la première approche, nous avons résolu le problème en utilisant une approche par force brute, et dans la seconde approche, nous avons encore optimisé la solution pour réduire la complexité temporelle.

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!

JavaScript Array 常量 for 循环 len 算法
Déclaration：
Cet article est reproduit dans:. en cas de violation, veuillez contacter admin@php.cn Supprimer
Article précédent：Qui a besoin d’AMP ? Simplifiez le processus de chargement paresseux des images réactives avec Layzr.jsArticle suivant：Qui a besoin d’AMP ? Simplifiez le processus de chargement paresseux des images réactives avec Layzr.js

Articles Liés

Voir plus