share my java solution using minheap!


  • 0
    T
    public class Solution {
        class node{
            int val;
            int index;
            int row;
            node(int a,int b,int c){
                this.val=a;
                this.index=b;
                this.row=c;
            }
        }
        public int[] smallestRange(int[][] nums) {
            PriorityQueue<node> pq=new PriorityQueue<>(1,new Comparator<node>(){
                   public int compare(node a,node b){
                       return a.val-b.val;
                   }
            });
            
            int[] res=new int[2];
            res[0]=Integer.MAX_VALUE;
            res[1]=Integer.MIN_VALUE;
            
            int[] temp=new int[2];
            
            for(int i=0;i<nums.length;i++){
                pq.offer(new node(nums[i][0],0,i));
                res[0]=Math.min(res[0],nums[i][0]);
                res[1]=Math.max(res[1],nums[i][0]);
            }
            temp[0]=res[0];
            temp[1]=res[1];
            
            while(!pq.isEmpty()){
                node t=pq.poll();
                int index=t.index;
                int row=t.row;
                if(index==nums[row].length-1){
                    break;
                }
                
                pq.offer(new node(nums[row][index+1],index+1,row));
                temp[0]=pq.peek().val;
                temp[1]=Math.max(temp[1],nums[row][index+1]);
                UpdateRange(res,temp);
            }
            return res;
            
        }
        
        public void UpdateRange(int[] res,int[] temp){
            if(res[1]-res[0]>temp[1]-temp[0]){
                res[0]=temp[0];
                res[1]=temp[1];
            }
        }
    }
    

Log in to reply
 

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