leetcode378+Kth Smallest Element in a Sorted Matrix+二分左小角判断开始

链接

//从左下角进行遍历,和之前那个找是否存在某个元素（右上角开始搜索）相反
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)/2;
            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 mid){
        int i=matrix.size()-1, j=0,cnt=0; //从左下角开始
        while(i>=0&&j<matrix[0].size()){
            if(matrix[i][j]<=mid){ //也是先从列开始
                j+=1;
                cnt += i+1; //那个元素所在的整列元素都小于 target。i的index从0开始的，所以要+1
            }else{ //再从行开始
                i-=1;
            }
        }
        return cnt;
    }
};