Share my 83ms java solution using PriorityQueue


  • 2
    public class Solution {
        private int[][] nums = null;
        private int col = 0;
        private int row = 0;
        
        public int kthSmallest(int[][] matrix, int k) {
            nums = matrix;
            col = matrix[0].length;
            row = matrix.length;
            
            HashSet<Integer> set = new HashSet<Integer>();
     
            PriorityQueue<Integer> pq = new PriorityQueue<Integer>(new Comparator<Integer>(){
                public int compare(Integer a, Integer b) {
                    return  nums[a/col][a%col] - nums[b/col][b%col]; 
                };
            });
            
            pq.offer(0);
            set.add(0);
            int n = 0;
            int num = 0;
            while (n < k && !pq.isEmpty()) {
                int tmp = pq.poll();
                num = nums[tmp/col][tmp%col];
                
                if (tmp+1 < row*col && !set.contains(tmp+1)) {
                    pq.offer(tmp+1);
                    set.add(tmp+1);
                }
                if (tmp+col < row*col && !set.contains(tmp+col)) {
                    pq.offer(tmp+col);
                    set.add(tmp+col);
                }
                n++;
            }
            
            return num;
        }
    }

Log in to reply
 

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