有序矩阵中第 K 小的元素 图解题解

这道题到底在问什么

输入

matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8

输出

13

解释

把所有数从小到大排：1,5,9,10,11,12,13,13,15，第 8 个是 13。

先想最直接的笨办法

数 ≤ x 不用挨个看。站在左下角：如果当前格 ≤ x，那它头顶这一整列（含自己）都 ≤ x，一次加一列、再往右走；如果当前格 > x，就往上缩。走一条阶梯线，只需 O(n) 步。（动画第 8 步）

最优解：一步一步想明白

1. 3行递增 + 列递增这是我们的例子。每行从左往右变大，每列从上往下变大。最小值在左上角（1），最大值在右下角（15）。第 K 小一定落在这两者之间。
2. 4全摊平 + 排序最直白：把矩阵所有数塞进一个数组，排个序，第 K 个就是答案。简单，但完全没用上「行列已经有序」这个宝贵条件。
3. 5浪费了有序性矩阵本来就半有序了，全摊开重排等于把现成的顺序信息扔掉重做。我们想要一个能吃下有序性的更快办法。
4. 6不猜「哪个格子」，猜「哪个值」反转思路：不去找第 K 小「在哪个格子」，而是在数值上二分。问自己：值 x 能不能当第 K 小？关键工具是「数出矩阵里 ≤ x 的有多少个」。
5. 7count(≤x) 随 x 单调不减把值域 [最小, 最大] 当作搜索区间。x 越大，count(≤x) 越大，这是单调的。我们要找最小的 x，使得 count(≤x) ≥ K——这个 x 必然是矩阵里真实存在的第 K 小。
6. 8从左下角走阶梯数 ≤ x 不用挨个看。站在左下角：如果当前格 ≤ x，那它头顶这一整列（含自己）都 ≤ x，一次加一列、再往右走；如果当前格 > x，就往上缩。走一条阶梯线，只需 O(n) 步。
7. 9lo=1 (左上) hi=15 (右下)值域下界 = 左上角最小值 1，上界 = 右下角最大值 15。我们在 [1,15] 这个数值区间上二分，而不是在格子位置上。
8. 10mid=(1+15)/2=8，指针落 (2,0)取 mid = (1+15)/2 = 8。开始数矩阵里 ≤ 8 的个数：指针落在左下角 (2,0)，那里的值是 12。
9. 11(2,0)=12 太大，i--当前格 12 大于 8。因为列是往下递增的，它下面只会更大，所以这一格不算、整列下半截都排除，指针上移到 (1,0)=10。
10. 12(1,0)=10 仍太大，i--10 还是 大于 8，继续上移到 (0,0)=1。注意我们一路只往上，从没回头——这就是阶梯走法只要 O(n) 步的原因。
11. 13(0,0)=1，列 0 全 ≤8：+11 ≤ 8！当前在第 0 行，所以从顶到这里只有 1 个格子 ≤8，count += 1。这一列处理完，指针右移到 (0,1)=5。
12. 14(0,1)=5 ≤8：count=25 ≤ 8，又是第 0 行，count 加到 2。右移到 (0,2)=9。
13. 15(0,2)=9 太大，i-- 越界结束9 大于 8，上移就越出了矩阵顶部，阶梯走完。count(≤8) = 2，远小于 8，说明第 8 小的值比 8 大。
14. 162 < 8 → lo = mid+1 = 9count 还不够 8，说明 mid=8 偏小，第 8 小一定 ＞8。把下界抬到 lo = 8+1 = 9，值域收窄成 [9,15]。二分区间砍掉一半。
15. 17mid=(9+15)/2=12，指针落 (2,0)新区间取 mid = (9+15)/2 = 12。再从左下角 (2,0) 起走一遍阶梯，当前值是 12。
16. 18(2,0)=12，列 0 三格全 ≤12(2,0)=12 ≤ 12，它在第 2 行（最底行），头顶整列 3 个都 ≤12，count += 3。右移到 (2,1)=13。
17. 19(2,1)=13 太大，i--(2,1)=13 大于 12，上移到 (1,1)=11。注意指针只往上、不回头。
18. 20(1,1)=11，上方 2 格 ≤12(1,1)=11 ≤ 12，它在第 1 行，从顶到这里有 2 个格子 ≤12，count 加到 5。右移到 (1,2)=13。
19. 21(1,2)=13 太大，i--(1,2)=13 又 大于 12，上移到 (0,2)=9。
20. 22(0,2)=9，第 0 行 +1，右移越界(0,2)=9 ≤ 12，第 0 行只 +1，右移就越出矩阵右边界，阶梯走完。count(≤12) = 6。
21. 236 < 8 → lo = mid+1 = 13count(≤12) = 6，还不到 8，第 8 小仍然比 12 大。下界抬到 lo = 13，区间收成 [13,15]。越来越逼近答案了。
22. 24mid=(13+15)/2=14，count=8mid = (13+15)/2 = 14。阶梯统计：(2,0)=12 那列贡献 3 个、(2,1)=13 贡献 3 个、(2,2)=15>14 上移、(1,2)=13 贡献 2 个，合计 count(≤14) = 8。
23. 258 ≥ 8 → hi = mid = 14count(≤14) = 8 ≥ 8 达标了！但 14 不一定是答案——可能有更小的值也满足。所以是 hi = mid = 14（保留 14，不减 1），继续往小处试。区间变 [13,14]。
24. 26mid=(13+14)/2=13，count=8mid = (13+14)/2 = 13。再走阶梯：12 那列 +3、13 那列 +3、15>13 上移、(1,2)=13 +2，合计还是 count(≤13) = 8。13 也满足！
25. 278 ≥ 8 → hi = 13，lo==hicount(≤13) = 8 仍 ≥ 8，于是 hi = 13。此刻 lo 和 hi 都等于 13，区间收成一个点，二分收敛，答案锁定。
26. 28lo == hi == 13 = 结果收敛到的 13 就是第 8 小。它必然是矩阵里真实存在的数：因为 count(≤13)=8≥8 且 count(≤12)=6<8，恰好在 13 这里跨过 K，所以 13 一定在矩阵中。整个过程没有真的去排序。
27. 29跨过 K 的那个值必然存在如果 x 不在矩阵里，那 count(≤x) 和 count(≤x-1) 会相等，x-1 也满足，x 就不会是「最小」的。所以二分停下来的值必然是矩阵里真实存在的数——这正是「二分答案」的精髓。
28. 30排序 → 二分值域每轮二分用 O(n) 阶梯统计一次，二分轮数是 log(最大值−最小值)。相比全摊开排序，又快又省空间（额外只用常数空间）。
29. 33记住这一句「二分答案」是个大套路：当答案具有单调判定性质（值越大越容易满足），就别去枚举位置，直接在数值范围上二分，配一个 O(n) 的计数器去判定。
30. 35若第 3 轮 hi=14-1=13 还好，但模式危险想象答案恰好就是当前 mid（红色这两个 13）。如果 count≥k 时贪图收快写成 hi=mid-1，就把可能是答案的 mid 排除了，区间会越过真值导致结果偏小。务必 hi=mid。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def kthSmallest(self, matrix, k):
        n = len(matrix)
        lo, hi = matrix[0][0], matrix[n-1][n-1]
        def count_le(x):
            i, j, cnt = n - 1, 0, 0
            while i >= 0 and j < n:
                if matrix[i][j] <= x:
                    cnt += i + 1
                    j += 1
                else:
                    i -= 1
            return cnt
        while lo < hi:
            mid = (lo + hi) // 2
            if count_le(mid) >= k:
                hi = mid
            else:
                lo = mid + 1
        return lo

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int n = matrix.size();
        int lo = matrix[0][0], hi = matrix[n-1][n-1];
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            int cnt = 0, i = n - 1, j = 0;
            while (i >= 0 && j < n) {
                if (matrix[i][j] <= mid) {
                    cnt += i + 1;
                    j++;
                } else {
                    i--;
                }
            }
            if (cnt >= k) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }
};

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 cnt = 0, i = n - 1, j = 0;
            while (i >= 0 && j < n) {
                if (matrix[i][j] <= mid) {
                    cnt += i + 1;
                    j++;
                } else {
                    i--;
                }
            }
            if (cnt >= k) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }
}

复杂度

面试官可能追问