LeetCode 378. 有序矩阵中第K小的元素——堆与二分的对比分析
LeetCode 378. 有序矩阵中第K小的元素——堆与二分的对比分析
适读人群：Java 中级工程师、备战面试的同学 | 阅读时长：约22分钟 | 难度：中等
开篇故事
这道题是我见过争议最大的算法题之一。网上一搜，堆解法和二分解法都有，各自的支持者还争来争去。
有人说堆解法直观易懂；有人说二分解法时间复杂度更优，才是真正的最优解。争了半天，其实两种方法都对，复杂度分析时考虑的维度不同罢了。
我在这篇文章里把两种方法都写出来，并做详细的复杂度对比，让你自己判断在不同场景下该选哪个。面试里两种都能答，但能对比分析清楚的候选人，会给面试官留下很深刻的印象。
一、题目解析
题目描述：
给你一个 n × n 矩阵 matrix，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
示例：
输入：matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
输出：13
输入：matrix = [[-5]], k = 1
输出：-5注意： 要的是第 k 小的元素（存在于矩阵中），不是第 k 小的不重复元素。
二、解法一：暴力排序
思路分析
把矩阵所有元素放入数组，排序后取第 k 个。
import java.util.*;
class Solution {
public int kthSmallest(int[][] matrix, int k) {
int n = matrix.length;
int[] arr = new int[n * n];
int idx = 0;
for (int[] row : matrix) {
for (int val : row) {
arr[idx++] = val;
}
}
Arrays.sort(arr);
return arr[k - 1];
}
}复杂度分析
- 时间复杂度：O(n² log n²) = O(n² log n)。
- 空间复杂度：O(n²)。
三、解法二：最小堆（多路归并）
思路分析
把矩阵的每一行看作一条有序链表，对所有行做多路归并，取第 k 个元素。
初始把第一列（每行第一个元素）放入最小堆，每次取出最小元素，并把该行的下一个元素入堆。重复 k 次。
import java.util.*;
class Solution {
public int kthSmallest(int[][] matrix, int k) {
int n = matrix.length;
// 最小堆，存 [val, row, col]
PriorityQueue<int[]> minHeap = new PriorityQueue<>(
(a, b) -> a[0] - b[0]
);
// 初始化：每行第一个元素
for (int i = 0; i < n; i++) {
minHeap.offer(new int[]{matrix[i][0], i, 0});
}
int result = 0;
for (int i = 0; i < k; i++) {
int[] cur = minHeap.poll();
result = cur[0];
int row = cur[1], col = cur[2];
if (col + 1 < n) {
minHeap.offer(new int[]{matrix[row][col + 1], row, col + 1});
}
}
return result;
}
}复杂度分析
- 时间复杂度：O(k log n)。k 次操作，每次堆操作 O(log n)（堆大小 n）。
- 空间复杂度：O(n)。
四、解法三（最优）：二分答案
核心思想
二分查找的对象不是下标，而是答案的值域。
矩阵最小值是 matrix[0][0]，最大值是 matrix[n-1][n-1]，在这个区间内二分。
对于一个中间值 mid，我们需要知道矩阵中有多少个元素 <= mid。如果这个数量 >= k，说明第 k 小的元素 <= mid，收缩右边界；否则收缩左边界。
如何 O(n) 统计 <= mid 的元素个数：
利用矩阵的有序性：从右上角出发，如果 matrix[i][j] <= mid，则这一列从 0 到 i 的元素都 <= mid，贡献 i+1 个，然后 j--；否则 i++。
完整代码
class Solution {
public int kthSmallest(int[][] matrix, int k) {
int n = matrix.length;
int lo = matrix[0][0], hi = matrix[n - 1][n - 1];
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
int count = countLessEqual(matrix, mid, n);
if (count >= k) {
hi = mid; // 第k小 <= mid，收缩右边界
} else {
lo = mid + 1; // 第k小 > mid，收缩左边界
}
}
return lo; // lo == hi 就是答案
}
/**
* 统计矩阵中 <= target 的元素个数
* 从右上角出发，O(n) 时间
*/
private int countLessEqual(int[][] matrix, int target, int n) {
int count = 0;
int row = 0, col = n - 1;
while (row < n && col >= 0) {
if (matrix[row][col] <= target) {
count += col + 1; // 这行前 col+1 个元素都 <= target
row++;
} else {
col--;
}
}
return count;
}
}复杂度分析
- 时间复杂度：O(n log(max-min))。二分范围是
[max-min]，最多 log(max-min) 次，每次 countLessEqual O(n)。 - 空间复杂度：O(1)。只用常数额外空间。
两种解法的对比
| 维度 | 堆解法 | 二分解法 |
|---|---|---|
| 时间 | O(k log n) | O(n log(max-min)) |
| 空间 | O(n) | O(1) |
| 适用场景 | k 很小时优势明显 | 值域范围小时优势明显 |
| 代码复杂度 | 简单直观 | 需要理解二分对象 |
何时用堆： k << n²，比如找第 1 个、第 2 个最小值。 何时用二分： k 接近 n²，或者矩阵值域不大时（如整数范围）。
五、举一反三
「二分答案 + 计数验证」是一类重要的题型：
| 题目 | 二分对象 | 验证函数 |
|---|---|---|
| 378 | 矩阵中的值 | 统计 <= mid 的元素数 |
| 410. 分割数组最大值 | 最大子数组和 | 验证能否用 m 段 |
| 875. 吃香蕉的速度 | 吃香蕉速度 | 验证 h 小时内是否吃完 |
六、踩坑实录
坑一：二分的左右边界是值域，不是下标
这道题二分的是矩阵元素的值，不是下标。lo = matrix[0][0]（最小值），hi = matrix[n-1][n-1]（最大值）。很多同学习惯了下标二分，一看到矩阵就想着 lo=0, hi=n*n-1，完全搞错了。
坑二：最终返回 lo 而非 lo 处的矩阵元素
lo 本身就是答案（矩阵中确实存在的元素），不需要 matrix[lo/n][lo%n]。二分的过程保证了 lo 一定是矩阵中的某个值。
坑三：countLessEqual 统计方向
从右上角还是左下角出发，逻辑不同，要确认自己的实现方向一致。这里选右上角：matrix[row][col] <= target 时，整列（0 到 row 行的 col 列）其实不对，应该是整行（0 到 col 列的 row 行）。
// 从右上角出发：(0, n-1)
// matrix[row][col] <= target: 这一行的前 col+1 个 <= target, row++
// matrix[row][col] > target: 这一列的后面都 > target, col--
count += col + 1; // 当前行，前 col+1 个元素
row++;七、总结
378 是「堆 vs 二分」对比的最好例子。两种方法都是最优解，选哪种取决于 k 和矩阵规模的关系。
掌握「二分答案 + O(n) 计数」这个模式，它在很多「第K小/大」问题上都能提供空间优异的解法，是进阶算法学习的重要节点。