Problem

Find the_k_th smallest number in at row and column sorted matrix.

Example

Given k =4and a matrix:

[
  [1 ,5 ,7],
  [3 ,7 ,8],
  [4 ,8 ,9],
]

return5

思路一(暴力)

• 将所有元素进行排序
• 时间复杂度: O(r * c)

思路二(heap)

• 从(0, 0)开始入heap, 然后弹出, 合成下方和右方元素, 并且用一个二维visited数组记录是否访问过.
• 所以要自定义一个类作为heap元素的类型, 包含坐标和数值.
• 时间复杂度: O(klogk)

    public int kthSmallest(int[][] matrix, int k) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return -1;
        }
        int r = matrix.length;
        int c = matrix[0].length;
        boolean[][] visited = new boolean[r][c];

        PriorityQueue<Point> heap = new PriorityQueue<>(1, new Comparator<Point>() {
            public int compare (Point p1, Point p2) {
                return p1.val - p2.val;
            }
        });
        heap.offer(new Point(0, 0, matrix[0][0]));
        while (!heap.isEmpty()) {
            Point p = heap.poll();
            k--;
            if (k == 0) {
                return p.val;
            }
            if (p.x + 1 < r && !visited[p.x + 1][p.y]) {
                heap.offer(new Point(p.x + 1, p.y, matrix[p.x + 1][p.y]));
                visited[p.x + 1][p.y] = true;
            }
            if (p.y + 1 < c && !visited[p.x][p.y + 1]) {
                heap.offer(new Point(p.x, p.y + 1, matrix[p.x][p.y + 1]));
                visited[p.x][p.y + 1] = true;
            }
        }
        return -1;
    }
    class Point {
        int x;
        int y;
        int val;
        public Point(int x, int y, int val) {
            this.x = x;
            this.y = y;
            this.val = val;
        }
    }