my long java solution using priorityQueue


  • 0
    F

    It is very slow, especially when k is large:

        static class Point implements Comparable<Point> {
            int x;
            int y;
            int val;
    
            public Point(int x, int y, int val) {
                this.x = x;
                this.y = y;
                this.val = val;
            }
    
            @Override
            public boolean equals(Object o) {
                if (this == o) return true;
                if (o == null || getClass() != o.getClass()) return false;
    
                Point point = (Point) o;
    
                return x == point.x && y == point.y && val == point.val;
    
            }
    
            @Override
            public int hashCode() {
                int result = x;
                result = 31 * result + y;
                result = 31 * result + val;
                return result;
            }
    
            @Override
            public int compareTo(Point o) {
                if (val != o.val) {
                    return Integer.compare(val, o.val);
                } else if (x != o.x) {
                    return Integer.compare(x, o.x);
                } else {
                    return Integer.compare(y, o.y);
                }
            }
        }
    
        public int kthSmallest(int[][] matrix, int k) {
            PriorityQueue<Point> priorityQueue = new PriorityQueue<>();
            int n = matrix.length;
            priorityQueue.offer(new Point(0, 0, matrix[0][0]));
            for (int i = 1; i < k; i++) {
                Point point = priorityQueue.poll();
                if (point.x + 1 < n) {
                    Point tmp = new Point(point.x + 1, point.y, matrix[point.x + 1][point.y]);
                    if (!priorityQueue.contains(tmp)) {
                        priorityQueue.offer(tmp);
                    }
                }
                if (point.y + 1 < n) {
                    Point tmp = new Point(point.x, point.y + 1, matrix[point.x][point.y + 1]);
                    if (!priorityQueue.contains(tmp)) {
                        priorityQueue.offer(tmp);
                    }
                }
            }
            return priorityQueue.poll().val;
        }

Log in to reply
 

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