Kth Smallest Element in a Sorted Matrix
给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第k小的元素。
请注意,它是排序后的第k小元素,而不是第k个元素。

示例:
matrix = [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,返回 13。

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

方法一:简单粗暴,遍历K次,每次找最小的值,将其赋值为MAX,这样第K次遍历找到的就是第K小的值

方法二:利用小顶堆(Java中的PriorityQueue优先队列),第K个出队的即为第k小的值
public static int kthSmallest(int[][] arr, int k) { PriorityQueue queue = new PriorityQueue<>(); for(int i = 0;i 0){ queue.poll(); } return queue.poll(); }
方法三:
直接求解矩阵中的第8小元素很难,我们可以用二分法设定一个值mid,查看mid值是否是矩阵第8小元素。
具体思路为:
1.首先设置mid的初值为矩阵matrix,最后一个数和第一个数的平均值。
2.统计矩阵中每一行小于mid值的个数之和。若该值小于8,记录当前mid,L = mid + 1,并更新mid;若该值大于8,R = mid - 1。
3.重复上述搜索,直至L和R不满足L <= R,此时的mid值即为所求。
public static boolean guess(int[][] matrix, int cur, int len, int k){ int sum = 0; for(int i = 0; i < len; i++){ int L = 0; int R = len - 1; int ans = 0; while (L <= R){ int mid = L + (R - L)/2; //若某一行值小于g,则应该是最后一个元素的下标 + 1. if(matrix[i][mid] < cur){ ans = mid + 1; L = mid + 1; }else { R = mid - 1; } } sum += ans; } System.out.println(sum); return k > sum; } public static int kthSmallest(int[][] matrix, int k) { //长度 int len = matrix.length; //最小的 int L = matrix[0][0]; //最大的 int R = matrix[len - 1][len - 1]; //答案 int res = 0; while (L <= R){ int mid = L + (R - L )/2; if(guess(matrix, mid, len, k)){ res = mid; L = mid + 1; }else { R = mid - 1; } } return res; }