Description

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

Solution

思路：对(x, y)点，下一个遍历的点事(x+1, y)和(x, y+1)中较小的那个点。故用到Priority Queue按点的大小排序，poll出(x,y)时，放(x+1, y)和(x, y+1)放回queue中
注意除了边界上的点，每个点都会遍历两次，因此要用visited去重

public class Solution {
    /*
     * @param matrix: a matrix of integers
     * @param k: An integer
     * @return: the kth smallest number in the matrix
     */

    public 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;
        }
    }

    public int kthSmallest(int[][] matrix, int k) {
        // write your code here
        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0 || k <= 0 || k > matrix.length * matrix[0].length) {
            return 0;
        }

        int n = matrix.length;
        int m = matrix[0].length;
        boolean[][] visited = new boolean[n][m];
        PriorityQueue<Point> pq = new PriorityQueue<Point>(k, new Comparator<Point>() {
            public int compare(Point a, Point b) {
                return a.val - b.val;
            }
        });

        pq.offer(new Point(0, 0, matrix[0][0]));
        visited[0][0] = true;
        while (k > 1) {
            Point cur = pq.poll();
            if (cur.x + 1 < n && !visited[cur.x + 1][cur.y]) {
                pq.offer(new Point(cur.x + 1, cur.y, matrix[cur.x + 1][cur.y]));
                visited[cur.x + 1][cur.y] = true;
            }

            if (cur.y + 1 < m && !visited[cur.x][cur.y + 1]) {
                pq.offer(new Point(cur.x, cur.y + 1, matrix[cur.x][cur.y + 1]));
                visited[cur.x][cur.y + 1] = true;
            }
            k--;
        }

        return pq.poll().val;
    }
}