ORID52 heap相关题目

378. Kth Smallest Element in a Sorted Matrix 解题报告

算法

为什么用这个算法？
这道题一开始真的没思路，所以跟着答案走了一遍。里面有一个思想很重要：从问题最简单的地方开始。
这道题问你在这个matrix里面第k小的数是多少，你要做的就是先从第1小的开始看。那么这个matrix既然已经从左到右，从上到下排好序了，那么左上角，也就是matrix[0][0] 肯定是最小的数。
这时候在找第二小的数字，那么只能是他右边或者下边的数，因为已经排好序了。
重复这个步骤，直到k次
那么heap就可以解决这个问题，你用minHeap来把最小的放到最前面，然后依次把最小的取出（因为你要第k小的数字）
每取出一次数之后，就把他右边或者下边最小的数放到这个堆里面。（这一步代码里面比较难实现，所以要练习）
做完k次循环之后，直接取heap里面第一个数的值就可以了。

代码实现

有什么要注意的地方？

class Solution {
    public class Pair {
        int x, y, val;
        public Pair(int x, int y, int val) {
            this.x = x;
            this.y = y;
            this.val = val;
        }
    }
    class PairComparator implements Comparator<Pair> {
        public int compare(Pair a , Pair b) {
            return a.val - b.val;
        }
    }
    public int kthSmallest(int[][] matrix, int k) {
        int[] dx = new int[] {0, 1};
        int[] dy = new int[] {1, 0};
        int n = matrix.length;
        int m = matrix[0].length;
        boolean[][] hash = new boolean[n][m];
        PriorityQueue<Pair> minHeap = new PriorityQueue<Pair>(k, new PairComparator());
        minHeap.add(new Pair(0, 0, matrix[0][0]));
        for (int i = 1; i < k; i++) {
            Pair cur = minHeap.poll();
            for (int j = 0; j < 2; j++) {
                int next_x = cur.x + dx[j];
                int next_y = cur.y + dy[j];
                Pair next_pair = new Pair(next_x, next_y, 0);
                if (next_x < n && next_y < m && !hash[next_x][next_y]) {
                    hash[next_x][next_y] = true;
                    next_pair.val = matrix[next_x][next_y];
                    minHeap.add(next_pair);
                }
            }
        }
        return minHeap.peek().val;
    }
}

时间空间复杂度

O(klogn)

哪些相关题目做过的？