373. Find K Pairs with Smallest Sums

Link

Solution

Merge sort : 先一輪nums2都是index 0的，然後最小的poll之後，num1 index不變，num2 index ++ 並放到queue中。如此持續K輪。

The run time complexity is O(kLogk) since queue.size <= k and we do at most k loop.

    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<int[]> queue = new PriorityQueue<>((a,b)-> a[0]+a[1]-b[0]-b[1]);
        List<List<Integer>> ret = new LinkedList<>();
        if(nums1.length==0 || nums2.length==0 || k==0) return ret;
        for(int i = 0; i < nums1.length; i++){
            queue.add(new int[]{nums1[i], nums2[0], 0});
        }
        
        while(k > 0 && !queue.isEmpty()){
            int[] cur = queue.poll();
            ret.add(Arrays.asList(cur[0], cur[1]));
            if(cur[2] < nums2.length-1){
                queue.add(new int[]{cur[0], nums2[cur[2]+1], cur[2]+1});
            }
            k--;
        }
        return ret;
    }