BiruLyu
7/28/2017 - 12:08 AM

373. Find K Pairs with Smallest Sums(#).java

public class Solution {
    public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        
        List<int[]> res = new ArrayList();
        
        if(nums1.length == 0 || nums2.length == 0 || k == 0) return res;
        
        PriorityQueue<int[]> q = new PriorityQueue<int[]>(new Comparator<int[]>(){
            public int compare(int[] a, int[] b){
                return a[0] + a[1] - b[0] - b[1];
            }
        });
        
        for(int i = 0; i < nums1.length && i < k; i++){
            q.offer(new int[] {nums1[i],nums2[0],0});
        }
        while(k-- > 0 && !q.isEmpty()){
            int[] temp = q.poll();
            res.add(new int[] {temp[0],temp[1]});
            if(temp[2] == nums2.length -1 ) continue;
            q.offer(new int[] {temp[0], nums2[temp[2]+1], temp[2]+1});
            
        }
        return res;
        
    }
}