JavaScript program to find median in row-sorted matrix

We will describe the process of finding the median in a row-sorted matrix using JavaScript. First, we will iterate over the matrix to collect all elements into an array. We then sort the array to find the middle value, which will be our median. If there is an even number of elements, the median is the average of the two middle values.

method

Given a row-sorted matrix, the median can be found by -

• Merge all rows into a sorted array.

• Find the middle element of the combined array, this will be the median.

• If the number of elements in the combined array is odd, return the middle element as the median.

• If the number of elements in the combined array is an even number, return the average of the two middle elements as the median.

• The time complexity of this method is O(m * n log (m * n)), where m is the number of rows in the matrix and n is the number of columns in the matrix.

  李>

• The space complexity is O(m * n) because the entire matrix needs to be combined into an array.

Example

This is a complete working example of a JavaScript function to find the median in a row-sorted 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));

illustrate

• findMedianThe function accepts a matrix as a parameter. It first calculates the total number and middle index (median) of elements in the matrix using totalElements and middleIndex respectively.

The

• start and end variables are initialized to the first and last elements of the matrix respectively, since they are the minimum and maximum values ​​in the matrix.

The above is the detailed content of JavaScript program to find median in row-sorted matrix. For more information, please follow other related articles on the PHP Chinese website!