跳到主要内容

LeetCode 378. 有序矩阵中第 K 小的元素

本节目标

在行列递增矩阵的值域中二分，并用左下到右上的阶梯路径统计排名。

这道题是分治与二分综合框架中的拓展题。矩阵每行、每列均按非递减顺序排列，但整体不按一维顺序存储；我们对可能的数值二分，而不是对坐标二分。

查看原题

题意与约束​

给定 n × n 矩阵 matrix，每行和每列均递增，返回所有元素按非递减排列后的第 k 小值。相同元素按出现次数计入排名。

朴素思路与瓶颈​

把 n² 个元素全部取出排序可以得到答案，但需要 O(n² log n) 时间和 O(n²) 额外空间。矩阵已经提供两维有序性，应把它用在“给定一个数值，能否快速知道它排在第几位”上。

对值域二分​

答案一定在左上角最小值与右下角最大值之间。对候选值 middle，令 count(middle) 为矩阵中不大于它的元素个数：

  • 若 count(middle) >= k，第 k 小值不大于 middle，保留左半值域；
  • 否则第 k 小值更大，丢弃 middle 及左半值域。

循环寻找第一个使计数达到 k 的数值。重复元素不会造成问题，因为我们求的是第一个满足阈值的值，而不是某个唯一坐标。

阶梯计数与单调性​

从左下角开始统计。当前元素 matrix[row][column] <= middle 时，该列从第 0 行到 row 行都不大于 middle，一次加入 row + 1 个并右移；否则当前行右侧都更大，只能上移。每一步至少减少一行或排除一列，总步数为 O(n)。

计数函数随候选值单调不减：若 x <= y，任何不大于 x 的元素也必不大于 y，所以 count(x) <= count(y)。这正是值域二分能找边界的条件，也说明“计数首次达到 k”就是第 k 小值。

代码实现​

两份源码都把搜索区间设为矩阵的最小、最大值，并保持“答案仍在 [left, right]”的不变量。计数函数只沿阶梯移动，不重新排序或使用堆。

C++17
#include <vector>
using namespace std;

class Solution {
private:
    int countNotGreaterThan(const vector<vector<int>>& matrix, long long value) {
        int row = static_cast<int>(matrix.size()) - 1;
        int column = 0;
        int count = 0;
        int size = static_cast<int>(matrix.size());

        while (row >= 0 && column < size) {
            if (matrix[row][column] <= value) {
                count += row + 1;
                column++;
            } else {
                row--;
            }
        }
        return count;
    }

public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        long long left = matrix[0][0];
        long long right = matrix.back().back();

        while (left < right) {
            long long middle = left + (right - left) / 2;
            if (countNotGreaterThan(matrix, middle) >= k) {
                right = middle;
            } else {
                left = middle + 1;
            }
        }
        return static_cast<int>(left);
    }
};

复杂度分析​

  • 时间复杂度：O(n log(valueRange))，其中每次阶梯计数为 O(n)。
  • 空间复杂度：O(1)，除固定数量变量外不创建额外容器。

易错点​

  • 从左上角开始却没有明确移动规则，导致重复扫描区域。
  • 统计 < middle，然后把边界更新当成 <= middle 的语义。
  • 把重复值去重，破坏题目按出现次数计算排名的定义。
  • 用堆作为主解法，忽略本题需要练习的值域二分与阶梯计数。

模式迁移​

二维有序结构常可以把“是否不大于某个阈值”转成单调路径计数。后续遇到行列单调矩阵、乘法表排名或二维阈值查询时，先检查是否能构造类似的计数函数；若只需逐步取出少量候选，才更适合选择堆。