Programme JavaScript pour trouver les valeurs maximales et minimales dans une matrice carrée

Pour trouver l'élément le plus grand ou le plus petit, il faut se concentrer sur le nombre de comparaisons à faire et sur la méthode à choisir pour la comparaison qui est la plus efficace : la méthode de comparaison d'éléments à l'aide d'instructions if-else ou la méthode de comparaison éléments utilisant des instructions if-else intégrées à. Nous verrons l’implémentation complète du code et son explication. Dans cet article, nous allons implémenter un programme JavaScript qui calcule les éléments les plus grands et les plus petits présents dans une matrice carrée donnée.

Introduction au problème

Cette question est simple, mais en approfondissant, vous découvrirez des concepts exceptionnels qui méritent d'être appris.

Dans ce problème, on nous donne une matrice pour laquelle nous devons trouver l'élément maximum et minimum qui y est présent. Par exemple, si la matrice est -

Mat = [ 1, 3, 7,
   5, 2, 9, 
   2, 5, 1]

À partir de la matrice ci-dessus, nous pouvons dire que 1 est l'élément minimum ou minimum et 9 est l'élément maximum ou maximum.

Voyons comment résoudre ce problème grâce à l'implémentation du code -

Méthode naïve

Dans cette méthode, nous allons simplement parcourir tous les éléments à la fois et vérifier s'ils sont plus grands que notre élément actuel. Les étapes suivantes seront suivies -

• Nous allons d'abord créer une fonction pour passer différentes matrices et obtenir le résultat

• Pour une matrice donnée, nous récupérerons ses lignes et ses colonnes afin de la parcourir à l'aide d'une boucle for.

• Nous allons créer deux variables pour stocker les éléments minimum et maximum et supposer que les éléments de la matrice sont inférieurs ou égaux à cette valeur et les initialiser à l'élément minimum 1000000000.

• De plus, nous initialiserons l'élément maximum à -1000000000 en supposant que les éléments de la matrice sont supérieurs ou égaux à cette valeur.

• À l'aide d'une boucle for, nous allons parcourir la matrice et pour chaque index, nous utiliserons deux conditions if-else.

• En effectuant les comparaisons requises, nous mettrons à jour les valeurs maximales et minimales.

Exemple

// creating a function to get the minimum and maximum number
function min_max(matrix){

   // getting rows and columns of given matrix
   var rows = matrix.length
   var cols = matrix[0].length
   var min_ans = 1000000000
   var max_ans = -1000000000
   
   // traversing over the matrix
   for(var i = 0; i<rows; i++){
      for(var j = 0; j<cols; j++){
         if(min_ans > matrix[i][j]){
            min_ans = matrix[i][j];
         }
         if(max_ans < matrix[i][j]) {
            max_ans = matrix[i][j];
         }
      }
   }
   console.log("The maximum element present in the Matrix is: " + max_ans);
   console.log("The minimum element present in the Matrix is: " + min_ans);
}

// defining the matrix
Mat = [ [1, 3, 7],
[5, 2, 9],
[2, 5, 1] ]

// calling the function
min_max(Mat)

Complexité temporelle et spatiale

La complexité temporelle du code ci-dessus est O(N*M), où N et M sont respectivement des lignes et des colonnes. De plus, la complexité spatiale est O(1).

Le problème principal ici n'est pas la complexité temporelle, mais le nombre de comparaisons que nous effectuons. Dans le code ci-dessus, nous effectuons des comparaisons N * M * 2 car pour chaque index nous vérifions les éléments minimum et maximum.

Une méthode plus efficace

Cette méthode est similaire à la méthode ci-dessus dans la plupart des cas, mais pour la partie comparaison, nous allons maintenant effectuer des comparaisons 3/2 * N* M en mettant à jour certaines instructions if-else. Regardons le code -

Exemple

// creating a function to get the minimum and maximum number
function min_max(matrix){

   // getting rows and columns of given matrix
   var rows = matrix.length
   var cols = matrix[0].length
   var min_ans = 1000000000
   var max_ans = -1000000000
   
   // traversing over the matrix
   for(var i = 0; i<rows; i++){
      for(var j = 0; j<=cols/2; j++){
         if (matrix[i][j] > matrix[i][rows - j - 1]){
            if (min_ans > matrix[i][cols - j - 1])
            min_ans = matrix[i][cols - j - 1];
            if (max_ans< matrix[i][j])
            max_ans = matrix[i][j];
         } else {
            if (min_ans > matrix[i][j])
            min_ans = matrix[i][j];
            if (max_ans < matrix[i][cols - j - 1])
            max_ans = matrix[i][cols - j - 1];
         }
      }
   }
   console.log("The maximum element present in the Matrix is: " + max_ans);
   console.log("The minimum element present in the Matrix is: " + min_ans);
}
// defining the matrix
Mat = [ [1, 3, 7],
[5, 2, 9],
[2, 5, 1] ]
// calling the function
min_max(Mat)

Complexité temporelle et spatiale

La complexité temporelle du code ci-dessus est O(N*M), où N et M sont respectivement des lignes et des colonnes. De plus, la complexité spatiale est O(1).

Le nombre de comparaisons ici est inférieur à celui d'avant, maintenant 3/2 * (N*M).

Conclusion

Dans ce tutoriel, nous allons implémenter un programme JavaScript qui calcule les éléments maximum et minimum présents dans une matrice carrée donnée. Nous parcourons la matrice donnée et comparons chaque élément avec la variable stockant la réponse. Deux techniques sont discutées : l'une avec des comparaisons 2*N*M et l'autre avec des comparaisons 3/2*N*M, mais les deux méthodes ont la même complexité spatiale.

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!