Programme JavaScript : comptez le nombre d'ensembles de 1 et de 0 dans une matrice binaire

Une matrice binaire est une matrice composée de seulement deux nombres qui, comme son nom l'indique, sont 1 et 0. Dans cet article, nous passerons en revue les codes et les explications appropriées pour mieux comprendre les concepts. Dans ce didacticiel, nous allons écrire un programme JavaScript pour calculer l'ensemble des 1 et des 0 dans une matrice binaire donnée.

Introduction au problème

Dans ce problème, on nous donne une matrice binaire et nous devons trouver l'ensemble de lignes ou de colonnes contenant la même valeur. Un ensemble peut être une valeur unique ou être de n'importe quelle taille, à condition qu'il contienne des éléments identiques provenant de lignes ou de colonnes. Par exemple,

Nous avons une matrice binaire avec deux lignes et trois colonnes qui ressemble à ceci -

1 0 1
0 0 1

Le nombre d'ensembles de 1 et 0 peut être calculé comme suit :

• Ensemble de taille 1 − Toutes les cellules de la matrice sont des ensembles distincts en soi et il y a un total de 6 cellules.

• Ensembles de taille 2 - Les deux premières colonnes de la deuxième ligne ont les mêmes valeurs, les deuxième et troisième colonnes ont également les mêmes valeurs, il y a 2 ensembles de taille 2 avec les mêmes valeurs. Il y a deux autres 1 dans la première ligne qui peuvent être considérés comme un ensemble

• Collection de taille 3 - La taille maximale possible de la collection dans une matrice est la taille maximale des lignes et des colonnes, ici elle est de 3. Cependant, pour la taille, aucun ensemble contenant la même valeur n'est disponible.

Nous avons donc 6, 3 et 0 sets disponibles pour les tailles 1, 2 et 3 respectivement. Donc finalement, notre réponse sera 9.

Méthode

Dans la section précédente, nous avons vu que nous devons nous concentrer uniquement sur une ligne ou une colonne particulière pour obtenir le nombre d'éléments similaires qu'elle contient. De plus, nous utiliserons un concept mathématique pour compter le nombre d'ensembles de tailles différentes présents. une ligne ou une colonne particulière.

Par exemple, si nous avons x nombre total de 1 d'affilée, alors le nombre total d'ensembles de 1 de tailles différentes de 1 à x proviendra de permutations.

Passons à cette approche –

• Tout d'abord, nous obtiendrons un tableau contenant des zéros et des uns, ou la matrice binaire donnée.

• Nous allons créer une fonction qui calcule automatiquement la réponse requise pour toute matrice qui lui est transmise en paramètre et renvoie la réponse comme valeur de retour.

• Dans cette fonction, nous allons parcourir le tableau ou la matrice binaire deux fois, une fois par lignes et une deuxième fois par colonnes.

• Dans la boucle for, nous maintiendrons deux variables, une pour stocker le nombre de 1 et l'autre pour stocker le nombre de 0.

• Après avoir parcouru une seule ligne ou colonne, nous mettrons à jour la réponse en utilisant la formule vue ci-dessus et stockerons la réponse dans notre variable.

• Enfin, nous renverrons la réponse en supprimant la ligne*colonne puisque nous les avons ajoutées deux fois.

Nous avons supprimé la colonne ligne * car lors de l'itération sur les lignes, l'ensemble est ajouté avec une valeur unique de deux zéros et un un et encore lors de l'itération sur les colonnes.

La traduction chinoise de

Exemple

est :

Exemple

Voyons la mise en œuvre des étapes ci-dessus pour mieux comprendre les concepts -

// given variables
var cols = 3; // no of columns
var rows = 2; // no of rows
// function to solve the problem with passed array 
function fun(arr) {
   // variable to store the final answer 
   var ans = 0;
   // traversing over the rows using for loop 
   for (var i = 0; i < rows; i++) {
      var ones = 0, zeroes = 0;
      for ( var j = 0; j < cols; j++) {
         if (arr[i][j] == 1)
         ones++;
         else
         zeroes++;
      }
      // increasing the answer on the basis of current count based on ones 
      ans = ans + Math.pow(2, ones)-1;
      // based on zeros 
      ans = ans + Math.pow(2, zeroes)-1;
   }
   //traversing over the columns using for loop 
   for (var i = 0; i < cols; i++) {
      var ones = 0, zeroes = 0;
      for ( var j = 0; j < rows; j++) {
         if (arr[j][i] == 1)
         ones++;
         else
         zeroes++;
      }
      //increasing the answer on the basis of current count based on ones 
      ans = ans + Math.pow(2, ones)-1;
      // based on zeros 
      ans = ans + Math.pow(2, zeroes)-1;
   }
   return ans - (rows * cols);
}
var arr = [ [ 1, 0, 1 ], [ 0, 1, 0 ] ];
console.log("Total number of the sets in the given binary matrix is: " + fun(arr));

Complexité temporelle et spatiale

La complexité temporelle du code ci-dessus est O(N*N), où N est le nombre maximum de lignes et de colonnes de la matrice donnée.

Aucun espace supplémentaire n'est utilisé, donc la complexité spatiale du code est O(1).

Conclusion

Dans ce tutoriel, nous avons appris à écrire un programme JavaScript qui compte le nombre d'ensembles de 1 et de 0 dans une matrice binaire donnée. Une matrice binaire est une matrice qui ne contient que deux nombres qui, comme son nom l'indique, sont 1 et 0. Le code en question a une complexité temporelle O(N*N) et une complexité spatiale O(1).

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!