leetcode 378. Kth Smallest Element in a Sorted Matrix

佚名 6年前 (2019-04-24) 随笔 1134人围观抢沙发百度已收录

二分的方法解决

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int left = matrix[0][0],right = matrix.back().back();
        while(left < right){
            int mid = left + (right - left)/2;
            int index = search(matrix,mid);
            if(index < k)
                left = mid + 1;
            else
                right = mid;
        }
        return left;
    }
    int search(vector<vector<int>>& matrix,int target){
        int i = matrix.size() - 1,j = 0,cnt = 0;
        while(i >= 0 && j < matrix[0].size()){
            if(matrix[i][j] <= target){
                j++;
                cnt += i + 1;
            }
            else
                i--;
        }
        return cnt;
    }
};