题目

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

思路

二分。。真想不到。。

由于矩阵的性质，每个元素的左上角的所有元素都小于等于它，所以可以从矩阵左下角开始遍历，可以在O(n)时间内找到所有小于等于某个元素的个数。二分，left = matrix[0][0], right = matrix[n - 1][n - 1]，第k小的元素肯定在这个区间内，所以对这个区间内的值进行二分。为什么最后left一定在矩阵中，因为边界是通过小于等于mid的个数确定的，在边界缩小的同时，k始终在这个边界中 ，且元素都为整数，在缩小到一个元素的时候即left == right，一定就是第k小元素。 class Solution { 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 - left) / 2; if(helper(matrix, k, mid)){ //严格小于的一定不是解 left = mid + 1; }else{ right = mid; } } return left; } boolean helper(int[][]matrix, int k, int mid){ int n = matrix.length; int i = n - 1, j = 0; int count = 0; while(i >=0 && j < n){ if(matrix[i][j] <= mid){ //第j列一共有i+1个元素小于等于mid count += i + 1; j++; }else{ i--; } } return count < k; } }