LeetCode|Java实现 LeetCode 378 有序矩阵中第K小的元素有序矩阵中第K小的元素|二分

378. 有序矩阵中第K小的元素 【LeetCode|Java实现 LeetCode 378 有序矩阵中第K小的元素】给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第k小的元素。
请注意，它是排序后的第k小元素，而不是第k个元素。
示例:

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

返回 13。
说明:
你可以假设 k 的值永远是有效的, 1 ≤ k ≤ n2 。

class Solution { public int kthSmallest(int[][] matrix, int k) { int n = matrix.length; int left = matrix[0][0], right = matrix[n-1][n-1]; while(left < right){ int mid = (left + right)/2; int cnt = numMid(matrix, n, mid); //System.out.println(cnt); if(cnt >= k){ right = mid ; } else { left = mid + 1; } } return right; }int numMid(int[][] matrix, int n, int mid){ int i = 0, j = n - 1; int cnt = 0; while(i=0){ if(matrix[i][j] > mid){ j--; } else { cnt += (j+1); i++; } } return cnt; } }