JavaScript-Programm zum Ermitteln des Medians in einer zeilensortierten Matrix

Wir beschreiben den Prozess der Ermittlung des Medians in einer zeilensortierten Matrix mithilfe von JavaScript. Zuerst durchlaufen wir die Matrix, um alle Elemente in einem Array zusammenzufassen. Anschließend sortieren wir das Array, um den Mittelwert zu finden, der unser Median ist. Bei einer geraden Anzahl von Elementen ist der Median der Durchschnitt der beiden Mittelwerte.

Methode

Bei einer nach Zeilen sortierten Matrix kann der Median durch -

ermittelt werden

• Alle Zeilen zu einem sortierten Array zusammenführen.

• Suchen Sie das mittlere Element des kombinierten Arrays. Dies ist der Median.

• Wenn die Anzahl der Elemente im kombinierten Array ungerade ist, geben Sie das mittlere Element als Median zurück.

• Wenn die Anzahl der Elemente im kombinierten Array eine gerade Zahl ist, wird der Durchschnitt der beiden mittleren Elemente als Median zurückgegeben.

• Die zeitliche Komplexität dieser Methode beträgt O(m * n log (m * n)), wobei m die Anzahl der Zeilen in der Matrix und n die Anzahl der Spalten in der Matrix ist.

  李>

• Die Raumkomplexität beträgt O(m * n), da die gesamte Matrix zu einem Array zusammengefasst werden muss.

Beispiel

Hier ist ein vollständiges Arbeitsbeispiel einer JavaScript-Funktion zum Ermitteln des Medians in einer zeilensortierten Matrix -

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));

Anleitung

Die Funktion

• findMedian akzeptiert eine Matrix als Parameter. Zunächst werden die Gesamtzahl und der mittlere Index (Median) der Elemente in der Matrix unter Verwendung von totalElements bzw. middleIndex berechnet.

Die Variablen

• start und end werden auf das erste bzw. letzte Element der Matrix initialisiert, da es sich um die minimalen und maximalen Werte in der Matrix handelt.

Das obige ist der detaillierte Inhalt vonJavaScript-Programm zum Ermitteln des Medians in einer zeilensortierten Matrix. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!