1. 概述
在本教程中，我们将讨论在一个每行有序的矩阵中查找中位数的问题。
首先我们会定义这个问题，并通过一个例子来说明。接着，我们会介绍两种解决方法，并给出它们的实现方式和时间复杂度分析。
2. 问题定义
假设我们有一个矩阵 M，它有 R 行且每行都已排序，每行有 C 列。我们的目标是找出该矩阵的中位数。⚠️ 注意：中位数是将所有元素排序后位于中间的那个元素。
举个例子，考虑如下这个每行有序的矩阵：
将所有元素展开排序后为 [1, 2, 4, 5, 7, 9]，总共有 6 个元素，中位数位于第 floor(6/2) = 5 个位置（从 0 开始），所以中位数是 5。
3. 简单暴力法（Naive Approach）
3.1 核心思想
✅ 将所有元素放入一个列表中，然后排序，最后取中间元素。
虽然这种方法思路简单，但效率不高，特别是当矩阵很大时，排序的开销会非常大。
3.2 实现代码
double medianNaive(int[][] M) {
int R = M.length;
int C = M[0].length;
List<Integer> list = new ArrayList<>();
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
list.add(M[i][j]);
}
}
Collections.sort(list);
int medianPos = (R * C) / 2;
return list.get(medianPos);
}
3.3 复杂度分析
- ✅ 时间复杂度：
O(R * C * log(R * C))，主要是排序的开销。 - ✅ 空间复杂度：
O(R * C)，需要额外存储所有元素。
4. 二分查找法（Binary Search）
4.1 核心思想
✅ 利用每行有序的特性，在数值范围内进行二分查找，判断当前中间值是否可能是中位数。
我们二分查找“可能的中位数值”，每一步都统计有多少个数小于等于当前中间值 mid，如果这个数量大于等于中位数的位置（即 (R * C) / 2），说明中位数可能在左边或就是 mid，否则说明中位数在右边。
4.2 辅助函数：统计小于等于 X 的元素个数
int countSmallerOrEqual(int[][] M, int X) {
int R = M.length;
int C = M[0].length;
int count = 0;
for (int i = 0; i < R; i++) {
int low = 0;
int high = C - 1;
int pos = C;
while (low <= high) {
int mid = low + (high - low) / 2;
if (M[i][mid] > X) {
pos = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
count += pos;
}
return count;
}
⚠️ 这个函数利用每行有序的特性，使用二分查找快速定位每行中小于等于 X 的元素个数。
4.3 主算法实现
int medianBinarySearch(int[][] M) {
int R = M.length;
int C = M[0].length;
int low = Integer.MIN_VALUE;
int high = Integer.MAX_VALUE;
int answer = 0;
while (low <= high) {
int mid = low + (high - low) / 2;
int count = countSmallerOrEqual(M, mid);
if (count >= (R * C + 1) / 2) {
answer = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
return answer;
}
⚠️ 注意这里 (R * C + 1) / 2 是为了兼容奇数和偶数长度的中位数逻辑（取中间偏左的那个）。
4.4 复杂度分析
- ✅ 时间复杂度：
O(32 * R * log C)- 32 是整数范围的二进制位数（相当于最多做 32 次二分查找）
- 每次二分查找对每行执行一次二分统计（
O(log C)）
- ✅ 空间复杂度：
O(1)，仅使用常量级额外空间
5. 总结
我们介绍了两种查找矩阵中位数的方法：
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 暴力法 | O(RC log RC) | O(RC) | 数据量小 |
| 二分法 | O(32 × R × log C) | O(1) | 数据量大、内存敏感 |
✅ 推荐使用二分法，尤其在数据量大、内存有限的场景下，效率更高且空间占用小。
⚠️ 踩坑提醒：
- 使用
floor((R * C) / 2)时注意奇偶性处理 - 二分查找边界要设置合理（
Integer.MIN_VALUE到Integer.MAX_VALUE） countSmallerOrEqual函数的逻辑要清晰，否则容易漏统计或错统计
如需进一步优化，可结合堆结构或归并排序思路，但上述二分法在多数情况下已足够高效。