我们将描述使用 JavaScript 在按行排序的矩阵中查找中位数的过程。首先，我们将遍历矩阵以将所有元素收集到一个数组中。然后，我们对数组进行排序以找到中间的值，这将是我们的中位数。如果元素个数为偶数，则中位数为中间两个值的平均值。
方法
给定一个按行排序的矩阵，可以通过以下方法找到中位数 -
将所有行合并到一个排序数组中。
-
找到组合数组的中间元素，这将是中位数。
立即学习“Java免费学习笔记（深入）”；
如果组合数组中的元素数量为奇数，则返回中间元素作为中位数。
如果组合数组中的元素个数为偶数，则返回中间两个元素的平均值作为中位数。
-
此方法的时间复杂度为 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变量分别初始化为矩阵的第一个和最后一个元素，因为它们是矩阵中的最小值和最大值.
