Programme JavaScript pour trouver la médiane dans une matrice triée par lignes

Nous décrirons le processus de recherche de la médiane dans une matrice triée par lignes à l'aide de JavaScript. Tout d’abord, nous allons parcourir la matrice pour collecter tous les éléments dans un tableau. Nous trions ensuite le tableau pour trouver la valeur médiane, qui sera notre médiane. S’il y a un nombre pair d’éléments, la médiane est la moyenne des deux valeurs médianes.

Méthode

Étant donné une matrice triée par lignes, la médiane peut être trouvée par -

• Fusionnez toutes les lignes dans un tableau trié.

• Trouvez l'élément central du tableau combiné, ce sera la médiane.

• Si le nombre d'éléments dans le tableau combiné est impair, renvoyez l'élément du milieu comme médiane.

• Si le nombre d'éléments dans le tableau combiné est un nombre pair, la moyenne des deux éléments du milieu est renvoyée comme médiane.

• La complexité temporelle de cette méthode est O(m * n log (m * n)), où m est le nombre de lignes dans la matrice et n est le nombre de colonnes dans la matrice.

  李>

• La complexité spatiale est O(m * n) car la matrice entière doit être combinée dans un tableau.

Exemple

Voici un exemple fonctionnel complet d'une fonction JavaScript pour trouver la médiane dans une matrice triée par lignes -

function findMedian(matrix) {
   
   // Get the total number of elements in the matrix
   const totalElements = matrix.length * matrix[0].length;
   
   // Calculate the middle index of the matrix
   const middleIndex = Math.floor(totalElements / 2);
   
   // Initialize start and end variables to keep track of the search space
   let start = matrix[0][0];
   let end = matrix[matrix.length - 1][matrix[0].length - 1];
    
   while (start <= end) {
   
      // Calculate the mid point
      let mid = Math.floor((start + end) / 2);
      
      // Initialize a counter to keep track of the number of elements less than or equal to the mid value
      let count = 0;
      
      // Initialize a variable to store the row index of the last element less than or equal to the mid value
      let rowIndex = -1;
          
      // Loop through each row in the matrix
      for (let i = 0; i < matrix.length; i++) {
      
         // Use binary search to find the first element greater than the mid value in the current row
         let columnIndex = binarySearch(matrix[i], mid);
         
         // If the current row has no element greater than the mid value, increment the count by the length of the row
         if (columnIndex === -1) {
            count += matrix[i].length;
            rowIndex = i;
         } else {
         
            // Otherwise, increment the count by the column index of the first element greater than the mid value
            count += columnIndex;
            break;
         }
      }
         
      // Check if the count of elements less than or equal to the mid value is greater than or equal to the middle index
      if (count >= middleIndex) {
         end = mid - 1;
      } else {
         start = mid + 1;
         rowIndex++;
      }
         
      // Check if we have reached the middle index
      if (count === middleIndex) {
         return matrix[rowIndex][middleIndex - count];
      }
   }
  
   return start;
}

// Helper function for binary search
function binarySearch(arr, target) {
   let start = 0;
   let end = arr.length - 1;
     
   while (start <= end) {
      let mid = Math.floor((start + end) / 2);
      if (arr[mid] === target) {
         return mid;
      } else if (arr[mid] < target) {
         start = mid + 1;
      } else {
         end = mid - 1;
      }
   }
     
   return start === 0 ? -1 : start - 1;
}
const arr = [
   [1, 2, 3], 
   [4, 5, 6], 
   [7, 8, 9]
];

console.log(findMedian(arr));

Instructions

La fonction

• findMedian accepte une matrice comme paramètre. Il calcule d'abord le nombre total et l'indice médian (médiane) des éléments de la matrice en utilisant respectivement totalElements et middleIndex .

Les variables

• start et end sont initialisées respectivement au premier et au dernier élément de la matrice, puisqu'elles sont les valeurs minimales et maximales de la matrice.

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!