Find the _k _th smallest number in at row and column sorted matrix.

Given k =4and a matrix:

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

return5

Solution 1: 从左上角元素开始，往右往下把元素加进pq，注意去重

    public int kthSmallest(int[][] matrix, int k) {
        // write your code here
        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 = 0; i < k - 1; 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;
    }
}

Solution 2: 先把每行第一个元素加进pq，再每次poll一个，加往右的下一个

    public int kthSmallest(int[][] matrix, int k) {
        class Node{
            int val, row, column;
            public Node(int val, int row, int column){
                this.val = val;
                this.row = row;
                this.column = column;
            }
        }

        PriorityQueue<Node> minHeap = new PriorityQueue<Node>(k, new Comparator<Node>(){
            public int compare(Node n1, Node n2){
                return n1.val - n2.val;
            }
        });

        int m = matrix.length;

        for(int i = 0; i < m; i++){
            if(matrix[i].length != 0){
                Node n = new Node(matrix[i][0], i, 0);
                minHeap.add(n);
            }    
        }

        for(int i = 0; i < k; i++){
            Node n = minHeap.poll();
            if(i == k - 1){
                return n.val;
            }
            if(n.column < matrix[n.row].length - 1){
                minHeap.add(new Node(matrix[n.row][n.column + 1], n.row, n.column + 1));
            }

        }

        return -1;
    }