目录

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

Shen 收录于每日一题

2021-10-25 约 729 字预计阅读 2 分钟

目录

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

如何判断一个数num在矩阵中处于第k小？从左下角向上移动，如果当前位置matrix[x][y] <= num，那么说明这一列前面所有的行都比该数小，那么叠加x+1，列向右移动y+=1。否则x向上移动(也就是行向上移动)，直到满足matrix[x][y] <= num或者移动出有序矩阵。
知道如何判断一个数处于第k大之后，那么我们可以将l=matrix[0][0], r=matrix[m-1][n-1]，对于这个区间内的数字进行二分查找，查找第一个满足处于第k小的元素。
这个元素一定在矩阵当中。举例[1, 2, 4, 10]，k=3，对任意数4<=x<10均满足在矩阵中满足条件的元素个数cnt=3，但是第一个满足cnt=3的元素一定是4，因为它包含等于的情况，也就是它自己。
$T:O(nlog(r-l))$，r是矩阵中的最大值，l是矩阵中的最小值，n是矩阵的大小

 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41


class Solution {
public:
    bool check(int t, vector<vector<int>>& matrix, int k) {
        int cnt = 0;
        int m = matrix.size(), n = matrix[0].size();

        // 查找左下角满足条件个数
        int x = m - 1, y = 0;
        while (x >= 0 && y < n) {
            if (matrix[x][y] <= t) {
                // 向右移动
                cnt += x + 1;
                y += 1;
            } else {
                // 向上移动
                x -= 1;
            }
        }
        // cnt >= k说明当前数过大，向左收缩边界
        return cnt >= k;
    }
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int m = matrix.size(), n = matrix[0].size();
        int l = matrix[0][0], r = matrix[m - 1][n - 1];

        // 二分查找第一个[(矩阵左下角小于等于该元素个数)大于等于k]的值。
        while (l < r) {
            int mid = ((r - l) >> 1) + l;
            if (check(mid, matrix, k)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }

        // l一定在矩阵当中
        // 因为第一个满足条件的个数大于等于k的元素肯定在矩阵中。
        // 如示例1 ,k = 8 时, res = 13, 当mid为14时也满足条件，但是由于我们找的是第一个，所以他会向左收缩边界(r = mid)。
        return l;
    }
};