JavaScript 在按行排序的矩阵中查找中位数

我们将使用JavaScript描述在按行排序的矩阵中查找中位数的过程。首先，我们将遍历矩阵，将所有元素收集到一个单一数组中。然后，我们将对数组进行排序，找到中间值，这将是我们的中位数。如果有偶数个元素，则中位数将是两个中间值的平均值。

方法

给定按行排序的矩阵，中位数可以通过以下方法找到：

• 将所有行组合成一个排序后的数组。

• 找到组合数组的中间元素或元素（们），这将是中位数。

• 如果组合数组的元素数是奇数，则将中间元素作为中位数返回。

• 如果组合数组的元素数是偶数，则将两个中间元素的平均值作为中位数返回。

• 该方法的时间复杂度为O(m * n log (m * n))，其中m是矩阵的行数，n是矩阵的列数。

• 空间复杂度为O(m * n)，因为整个矩阵需要组合成一个单一数组。

示例

以下是一个完整的工作示例，用于在按行排序的矩阵中查找中位数的JavaScript函数：

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

解释

• findMedian 函数以一个矩阵作为参数。首先使用 totalElements 和 middleIndex 分别计算矩阵中元素的总数和中间索引（中位数）。

• start 和 end 变量分别初始化为矩阵的第一个和最后一个元素，因为它们是矩阵中的最小值和最大值。