给定一个 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; Queue<Integer> q = new PriorityQueue<>((o1,o2) -> (o2 - o1)); for(int i = 0 ; i < n ; i++) for(int j = 0 ; j < n ; j++){ if(q.size() < k) q.add(matrix[i][j]); else if(matrix[i][j] < q.peek()){ q.poll(); q.add(matrix[i][j]); } } return q.peek(); } }用的优先级队列。
我挂一下大佬写的二分代码吧···甘拜下风。突出一个牛皮
class Solution { public int kthSmallest(int[][] matrix, int k) { int n = matrix.length-1; int l = matrix[0][0], r = matrix[n][n]; while(l < r) { int mid = l + (r-l)/2; int count = countNoMoreThanMid(matrix, mid, n); if(count < k) l = mid+1; else r = mid; } return r; } public int countNoMoreThanMid(int[][] matrix, int mid, int n) { int x = n, y = 0, count = 0; while(x >= 0 && y <= n) { if(matrix[x][y] <= mid) { count += x + 1; ++ y; }else { -- x; } } return count; } }