Leetcode 378. 有序矩阵中第 K 小的元素（中等）_有序矩阵中第k小的元素 复杂度

题目

给你一个 $n\times n$ 矩阵 matrix ，其中每行和每列元素均按升序排序，找到矩阵中第 $k$ 小的元素。
请注意，它是 排序后 的第 $k$ 小元素，而不是第 $k$ 个 不同 的元素。

示例 1：

输入：matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
输出：13
解释：矩阵中的元素为 [1,5,9,10,11,12,13,13,15]，第 8 小元素是 13
1
2
3

示例 2：

输入：matrix = [[-5]], k = 1
输出：-5
1
2

提示：

• $n==matrix.length$
• $n==matrix[i].length$
• $1<=n<=300$
• $-10^9<=matrix[i][j]<=10^9$
• 题目数据 保证 matrix 中的所有行和列都按 非递减顺序 排列
• $1<=k<=n^2$

题解

由题目给出的性质可知，这个矩阵内的元素是从左上到右下递增的（假设矩阵左上角为 matrix[0][0]）。以下图为例：

我们知道整个二维数组中 matrix[0][0]为最小值，matrix[n - 1][n - 1] 为最大值，现在我们将其分别记作 l 和 r。

可以发现一个性质：任取一个数 mid 满足 l ≤ mid ≤ r，那么矩阵中不大于 mid 的数，肯定全部分布在矩阵的左上角。

例如下图，取 mid=8：

我们可以看到，矩阵中大于 mid的数就和不大于 mid 的数分别形成了两个板块，沿着一条锯齿线将这个矩形分开。其中左上角板块的大小即为矩阵中不大于 mid 的数的数量。

我们只要沿着这条锯齿线走一遍即可计算出这两个板块的大小，也自然就统计出了这个矩阵中不大于 mid 的数的个数了。

走法演示如下，依然取 mid=8：

可以这样描述走法：

• 初始位置在 matrix[n - 1][0]（即左下角）；

• 设当前位置为 matrix[i][j]。若 matrix[i][j] ≤ mid，则将当前所在列的不大于 mid 的数的数量（即 i + 1）累加到答案中，并向右移动，否则向上移动；

• 不断移动直到走出格子为止。

我们发现这样的走法时间复杂度为 $O(n)$，即我们可以线性计算对于任意一个 mid，矩阵中有多少数不大于它。这满足了二分查找的性质。

不妨假设答案为 x，那么可以知道 l ≤ x ≤ r，这样就确定了二分查找的上下界。

每次对于「猜测」的答案 mid，计算矩阵中有多少数不大于 mid ：

• 如果数量不少于 k，那么说明最终答案 x 不大于 mid；
• 如果数量少于 k，那么说明最终答案 x 大于 mid。

这样我们就可以计算出最终的结果 x 了。

【代码】

class Solution {
public:
    int getCnt(vector<vector<int>>& matrix, int val) { //找到不大于val的数的个数
        int x = matrix.size() - 1, y = 0, cnt = 0;
        while(x >= 0 && y < matrix.size()) {
            if (matrix[x][y] <= val) { //左下角的数
                cnt += x + 1;
                y++;
            } else {
                x--;
            }
        }
        return cnt;
    }

    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int n = matrix.size();
        int left = matrix[0][0], right = matrix[n - 1][n - 1];
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (getCnt(matrix, mid) < k) left = mid + 1;
            else right = mid;
        }
        return left;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

【复杂度分析】

• 时间复杂度：$O(nlog(r-l))$，二分查找进行次数为 $O(log(r-l))$，每次操作时间复杂度为 $O(n)$。
• 空间复杂度：$O(1)$。

题解分析来源于官方题解。