无法播放？请 点击这里 跳转到Youtube
切换视频源：

题目链接: https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/

GitHub答案源代码请点击这里

2D Heap BFS2 解法

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        PriorityQueue<Coord> minHeap = new PriorityQueue<>((a, b) -> a.val - b.val);
        minHeap.offer(new Coord(0, 0, matrix[0][0]));
        boolean[][] visited = new boolean[n][n];
        for (int v = 0; v < k - 1; v++) {
            Coord top = minHeap.poll();
            if (top.i + 1 < n && !visited[top.i + 1][top.j]) {
                visited[top.i + 1][top.j] = true;
                minHeap.offer(new Coord(top.i + 1, top.j, matrix[top.i + 1][top.j]));
            }
            if (top.j + 1 < n && !visited[top.i][top.j + 1]) {
                visited[top.i][top.j + 1] = true;
                minHeap.offer(new Coord(top.i, top.j + 1, matrix[top.i][top.j + 1]));
            }
        }
        return minHeap.peek().val;
    }
}

展开成1D套用215题

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        int[] arr = new int[n * n];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = matrix[i / n][i % n];
        }
        
        PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
        for (int x : arr) {
            if (heap.size() < k || x <= heap.peek()) {
                heap.offer(x);
            }
            
            if (heap.size() > k) {
                heap.poll();
            }
        }
        return heap.peek();
    }
}