BFS-Like solution: go through all candidate.


  • 0
    F
    // greedy idea, a number can be candidate, only if the up/left number is checked.
        // every number is checked out, only consider if the right/ down number can be candidate.
        // by this two condidation, we can go through matrix to get the result.
        // iterate this process.
        // like bfs.
        public class Point {
            int x, y, value;
            Point(int x, int y, int value) {
                this.x = x;
                this.y = y;
                this.value = value;
            }
        }
        public int kthSmallest4(int[][] matrix, int k) {
            if (matrix.length == 0 || matrix[0].length == 0) return 0;
            Queue<Point> queue = new PriorityQueue<Point>(new Comparator<Point>(){
               @Override
               public int compare(Point p1, Point p2) {
                   return p1.value-p2.value;
               }
            });
            int m = matrix.length, n = matrix[0].length;
            queue.offer(new Point(0, 0, matrix[0][0]));
            int count = 1;
            Point p = null;
            while (count < k) {
                p = queue.poll();
                count++;
                matrix[p.x][p.y] = Integer.MAX_VALUE;
                // right
                if (p.y+1 != n && (p.x == 0 || matrix[p.x-1][p.y+1] == Integer.MAX_VALUE)) 
                queue.offer(new Point(p.x, p.y+1, matrix[p.x][p.y+1]));
                // down
                if (p.x+1 != m && (p.y == 0 || matrix[p.x+1][p.y-1] == Integer.MAX_VALUE)) 
                queue.offer(new Point(p.x+1, p.y, matrix[p.x+1][p.y]));
            }
            return queue.poll().value;
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.