[378. 有序矩阵中第K小的元素]

[378. 有序矩阵中第K小的元素]

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

示例：

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

返回 13。

思路 ： 在Matrix[0][0]~Matrix[length-1][length-1]之间二分查找一个数n, 遍历数组如果小于等于n的个数大于K, 则右边界缩小为n，反之左边界放大到n+1

public class Q378 {
    public int kthSmallest(int[][] matrix, int k){
        int n = matrix.length;
        int left = matrix[0][0];
        int right = matrix[n-1][n-1];

        while (left < right){
            int mid = (left + right)>>1;
            if(check(matrix, k, mid)){
                right = mid;
            }else {
                left = mid+1;
            }
        }
        return left;
    }

    private boolean check(int[][] m ,int k , int n){
        int sum = 0;
        int num = 0;
        int i = m.length-1;
        int j = 0;

        while (i >= 0){
            if(m[i][j] <= n){
                num++;
                j++;
                if(j >= m.length){
                    sum += num*(i+1);
                    break;
                }
            }else {
                i--;
                sum += num;
            }
        }

        return sum >= k;
    }

    public static void main(String[] args) {
        System.out.println(new Q378().kthSmallest(new int[][]{{1, 5, 9}, {10, 11, 13}, {12, 13, 15}}, 8));
    }
}