Maison >interface Web >js tutoriel >Programme Javascript pour compter les 1 dans un tableau binaire trié

Programme Javascript pour compter les 1 dans un tableau binaire trié

WBOYavant: 2023-08-23 21:57:13759parcourir

Javascript 程序对已排序的二进制数组中的 1 进行计数

Nous avons deux façons de compter 1 dans un tableau binaire trié. La première consiste à parcourir le tableau et à compter le nombre de 1. La deuxième méthode consiste à utiliser l'algorithme de recherche binaire pour trouver la première occurrence de 1 dans le tableau.

Il est important de noter que pour utiliser ces méthodes, le tableau doit être trié.

Dans cet article de blog, nous discuterons d'un programme JavaScript permettant de compter le nombre de 1 dans un tableau binaire trié. Nous examinerons également certains cas extrêmes et techniques d'optimisation pour rendre le programme plus efficace.

Énoncé du problème

Étant donné un tableau binaire trié, la tâche consiste à compter le nombre de 1 dans le tableau. Les tableaux peuvent être de n'importe quelle taille et leurs éléments ne peuvent être que 0 ou 1.

Entrez

 bin_array[] = {0, 0, 0,1,1,1}

Sortie

Méthode 1

La première approche qui me vient à l'esprit consiste à parcourir le tableau et à compter le nombre de 1.

Initialisez une variable de comptage pour stocker le nombre dans le tableau.
Parcourez le tableau et vérifiez chaque élément. Si l'élément courant est égal à 1, incrémentez le compteur.

Exemple

<html>
<body>
   <p id="result1"></p>
   <p id="result2"></p>
   <script>
      function count_num_of_Ones( bin_array,n) {
         let num_of_ones=0;
         for (let ind = 0; ind < n; ind++) {
            if(bin_array[ind]==1){
               num_of_ones++;
            }
         }
         return num_of_ones;
      }
      let bin_array = [0,0,0,1,1,1];
      let n = bin_array.length;
      document.getElementById("result1").innerHTML = "Original Array: " + JSON.stringify(bin_array);
      document.getElementById("result2").innerHTML = "Count of 1's in given array is " + count_num_of_Ones(bin_array,n)
   </script>
</body>
</html>

Cependant, la complexité temporelle de cette approche est O(n), où n est la taille du tableau, puisque nous parcourons l'ensemble du tableau une fois.

Cela peut être optimisé en profitant du fait que le tableau est trié.

Méthode 2

Pour trouver la première instance de 1 dans un tableau, utilisez la méthode de recherche binaire. Soustrayez simplement l’index de la première instance du nombre total d’éléments du tableau pour obtenir le nombre de 1.

Dans cette implémentation, nous utilisons la technique de recherche binaire "première occurrence" pour trouver la première instance de 0 dans le tableau.
Les variables low et high sont initialement définies sur le premier et le dernier index du tableau en conséquence.
Le nombre d'éléments dans le tableau est également spécifié comme valeur d'une variable appelée firstOne, qui sera utilisée pour enregistrer l'index de la première instance du nombre 1.
La boucle while continuera à s'exécuter jusqu'à ce que l'indice bas soit supérieur ou égal à l'indice haut. Après chaque itération, nous déterminons le point médian de la plage actuelle.
Si l'élément du milieu est 1, mettez à jour la variable firstOne et déplacez l'index élevé vers l'élément précédent. Si l'élément au milieu est 0, nous déplaçons l'index inférieur vers l'élément suivant.
Une fois la boucle while terminée, nous vérifions si la première variable correspond à la valeur -1 du tableau. Si c'est le cas, cela signifie qu'il n'y a pas de 1 dans le tableau, donc 1 est renvoyé. Sinon, retournez firstOne moins arr.length.

Exemple

<html>
<body>
   <p id="result1"></p>
   <p id="result2"></p>
   <script>
      function count_num_of_Ones(bin_arr,low,high) {
         var low = 0;
         var high = bin_arr.length - 1;
         var firstOne = -1;
         while (low <= high) {
            var mid = Math.floor((low + high) / 2);
            if (bin_arr[mid] == 1) {
               firstOne = mid;
               high = mid -1;
            } else {
               low = mid + 1;
            }
         }
         return firstOne == -1 ? 0 : bin_arr.length - firstOne;
      }
      let bin_array = [0,0,0,1,1,1,1];
      let n = bin_array.length;
      document.getElementById("result1").innerHTML = "Original Array: " + JSON.stringify(bin_array);
      document.getElementById("result2").innerHTML = "Count of 1's in given array is " + count_num_of_Ones(bin_array,n)
   </script>
</body>
</html>

La complexité temporelle de cette méthode est O(log n), ce qui est beaucoup plus efficace que la méthode précédente.

Dans ce tutoriel, nous avons discuté d'un programme JavaScript permettant de compter le nombre de 1 dans un tableau binaire trié.

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!

Déclaration：

Cet article est reproduit dans:. en cas de violation, veuillez contacter admin@php.cn Supprimer

Article précédent：Comment obtenir la hauteur du texte mise à l'échelle à l'aide de FabricJS ?Article suivant：Comment obtenir la hauteur du texte mise à l'échelle à l'aide de FabricJS ?

Articles Liés

Voir plus