给定一个 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)); } }