给定一个 n x n 矩阵，其中每一行和每一列都按升序排序，找到矩阵中第 k 个最小的元素。

请注意，它是排序顺序中的第 k 个最小元素，而不是第 k 个不同的元素。

例子：

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

k = 8,

返回 13。

Java 解决方案

这种排序矩阵的起点是左下角。

public int kthSmallest(int[][] matrix, int k) {
    int m=matrix.length;
 
    int lower = matrix[0][0];
    int upper = matrix[m-1][m-1];
 
    while(lower<upper){
        int mid = lower + ((upper-lower)>>1);
        int count = count(matrix, mid);
        if(count<k){
            lower=mid+1;
        }else{
            upper=mid;
        }
    }
 
    return upper;
}
 
private int count(int[][] matrix, int target){
    int m=matrix.length;
    int i=m-1;
    int j=0;
    int count = 0;
 
    while(i>=0&&j<m){
        if(matrix[i][j]<=target){
            count += i+1;
            j++;
        }else{
            i--;
        }
    }
 
    return count;
}