LeetCode第378题 有序矩阵中第K小的元素_有序矩阵寻找第k小

问题：

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

示例1：

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

输出：13

解释：矩阵中的元素为[1, 5, 9, 10, 11, 12, 13, 13, 15], 第8小元素是13。

提示：

n == matrix.length

n == matrix[i].length

解答：

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k){
    int mArrSize = matrix.size(); //矩阵大小
    int left = matrix[0][0]; //矩阵有序排列，第0行第0列即为最小值
    int right = matrix[mArrSize-1][mArrSize-1]; //最后一列最后一列即为最大值
    int mid = 0;  
    int count = 0;  
    while(left < right){
        mid = left + (right - left)/2; //left和right的中间值
        count = nBcount(matrix, mid);  //计算矩阵中小于mid的元素的数量count
        if(count < k){  //小于mid的元素数量比k小时，说明目标在mid的右侧
            left = mid+1;  //将左极限更新为mid
        }else {
            right = mid; //目标在mid左侧时，将右极限更新为mid
        }
    }
    return right; //最终right=left时退出while循环，right或left即为最终结果
}
 
private:
    int nBcount(vector<vector<int>> & matrix, int n)
{
    int row = matrix.size()-1;
    int mCol = matrix[0].size();
    int col=0;
    int count = 0;
    while(row>=0 && col<mCol){
        if(matrix[row][col]<= n){
            count += row + 1;
            col++;
        }else{
            row--;
        }
    }
    return count;
}
 
};