LeetCode 378. 有序矩阵中第K小的元素_leetcode378完整代码

题目描述：
给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。

示例：

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

返回 13。

思路：
二分法，由于从左到右，从上到下都是升序，所以当定义一个元素，会有一条分割线，左上部分的数都是小于该元素的，坐下都是大于该元素，利用这一规律，找到，数量等于k的分割点

class Solution {
public:
    bool check(vector<vector<int>>&matrix,int mid,int k,int n){
        int i=n-1;
        int j=0;
        int num=0;
        while(i>=0&&j<=n-1){
            if(matrix[i][j]<=mid){
                j++;
                num+=i+1;
            }
            else{
                i--;
            }
        }
        return num>=k;
    }
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int n=matrix.size();
        int left=matrix[0][0];
        int right=matrix[n-1][n-1];
        while(left<right){
            int mid=left+(right-left)/2;
            if(check(matrix,mid,k,n)){
                right=mid;
            }
            else{
                left=mid+1;
            }
        }
        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
27
28
29
30
31
32
33