Day92 有序矩阵中第 K 小的元素

给你一个 n x n 矩阵 matrix ，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。

请注意，它是 排序后 的第 k 小元素，而不是第 k 个 不同 的元素

https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix/

示例1：

1 ,5 , 9

10,11,13

12,13,15

输入：matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
输出：13
解释：矩阵中的元素为 [1,5,9,10,11,12,13,13,15]，第 8 小元素是 13

示例2：

输入：matrix = [[-5]], k = 1
输出：-5

提示：

n == matrix.length
n == matrix[i].length
1 <= n <= 300
-109 <= matrix[i][j] <= 109
题目数据 保证 matrix 中的所有行和列都按 非递减顺序 排列
1 <= k <= n2

Java解法

思路：

• 做矩阵的题脑子总是自动想成正方形，这次可算是正方形了，最简单的方法，有序数组合并，遍历查找

• 设想1：矩阵边界处理，对两个有序列表寻找第k大

• 设想2：参考官方归并思路，对N个有序列表寻找 第k大即可，这里用到了最小堆的概念，实际上这个矩阵可以部分看成一个重叠的最小堆

package sj.shimmer.algorithm.m4_2021;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * Created by SJ on 2021/4/29.
 */

class D92 {
    public static void main(String[] args) {
        int[][] matrix = {
            {1, 4, 7, 11, 15},
            {2, 5, 8, 12, 19},
            {3, 6, 9, 16, 22},
            {10, 13, 14, 17, 24},
            {18, 21, 23, 26, 30},
        };
        System.out.println(kthSmallest(matrix,10));
        System.out.println(kthSmallest(matrix,14));
        matrix = new int[][]{
            {-5},
        };
        System.out.println(kthSmallest(matrix,1));
        matrix = new int[][]{
            {1  ,5  ,  9},
            {10,11,13},
            {12,13,15},
        };
        System.out.println(kthSmallest(matrix,8));

        matrix = new int[][]{
            {1,3,5},
            {6,7,12},
            {11,14,14}
        };
        System.out.println(kthSmallest(matrix,3));


    }
    public static int kthSmallest(int[][] matrix, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                return a[0] - b[0];
            }
        });
        int n = matrix.length;
        for (int i = 0; i < n; i++) {
            pq.offer(new int[]{matrix[i][0], i, 0});
        }
        for (int i = 0; i < k - 1; i++) {
            int[] now = pq.poll();
            if (now[2] != n - 1) {
                pq.offer(new int[]{matrix[now[1]][now[2] + 1], now[1], now[2] + 1});
            }
        }
        return pq.poll()[0];
    }
    public static int kthSmallestError(int[][] matrix, int k) {
        if (matrix == null) {
            return 0;
        }
        int n = matrix.length;
        int index = 0;
        for (int i = 1; i < n+1; i++) {
            if (k> i * i) {
                continue;
            }else if (k== i * i){
                return matrix[i - 1][i - 1];
            }else {
                k = k- (i-1) * (i-1);
                index = i-1;
                break;
            }
        }
        int x = 0;
        int y = 0;
        while (k > 0) {
            k--;
            if (matrix[index][x]>matrix[y][index]) {
                if (k==0) {
                    return matrix[y][index];
                }
                y++;
            }else {
                if (k==0) {
                    return matrix[index][x];
                }
                x++;
            }
        }
        return 0;
    }
}

image

官方解

https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix/solution/you-xu-ju-zhen-zhong-di-kxiao-de-yuan-su-by-leetco/

1. 直接排序：最简单的处理

2. 归并排序：大佬的解释更易懂：归并排序

3. 二分查找：这个角度厉害，能利用到二分查找效率最高