有序矩阵中第K小的元素

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小的值

1
2
3
4
5
6
7
8
9
10
11
12
13
public static int kthSmallest(int[][] arr, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for(int i = 0;i<arr.length;i++){
            for(int j = 0;j<arr[0].length;j++){
                queue.add(arr[i][j]);
            }
        }
        //System.out.println(queue.);
        while(--k > 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值即为所求。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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;
    }
0 条评论
发表一条评论