目录

• 题目描述：
• 示例:
• 解法：

题目描述：

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

示例:

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

返回 13。

说明:

• 你可以假设 k 的值永远是有效的, 1 ≤ k ≤ n2 。

---

解法：

class Solution {
public:
    int binarySearch(vector<int>& lst, int l, int r, int target){
        int mid = 0;
        while(l <= r){
            mid = l + (r - l)/2;
            if(lst[mid] <= target){
                l = mid +1;
            }else{
                r = mid-1;
            }
        }
        return l;
    }
    
    int search(vector<vector<int>>& matrix, int m, int n, int k, int l, int r){
        // cout<<"l="<<l<<", r="<<r<<", k="<<k<<endl;
        if(l == r){
            return l;
        }
        int mid = l + (r - l)/2;
        int cnt = 0;    // num <= mid
        for(int i = 0; i < m; i++){
            int idx = binarySearch(matrix[i], 0, n-1, mid);
            cnt += idx;
        }
        if(cnt < k){
            l = mid + 1;
        }else{
            r = mid;
        }
        return search(matrix, m, n, k, l, r);
    }
    
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int m = matrix.size();
        int n = matrix[0].size();
        int l = matrix[0][0], r = matrix[m-1][n-1];
        if(k == 1){
            return matrix[0][0];
        }else{
            return search(matrix, m, n, k, l, r);
        }
    }
};