Java 8ms easy to understand solution


  • 0
    S

    Maintain an array to record the current pair index of nums2 to nums1. E.g, the 0th item of the array is the current index of the nums2 that combine a pair to the 0th number. And we keep a heap to get the minimum sum of the nums1.length pair.

    public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
            k = Math.min(k, nums1.length * nums2.length);
            List<int[]> result = new ArrayList<>();
            if(nums1.length == 0 || nums2.length == 0) return result;
            int[] index1 = new int[nums1.length];
            PriorityQueue<Node> q = new PriorityQueue<>(new Comparator<Node>(){
                public int compare(Node n1, Node n2){
                    return n1.sum - n2.sum;
                }
            });
            for(int i = 0; i < nums1.length; i++)
                q.add(new Node(i, nums1[i] + nums2[0]));
            for(int i = 0; i < k; i++){
                Node temp = q.poll();
                result.add(new int[] {nums1[temp.index], nums2[index1[temp.index]]});
                index1[temp.index]++;
                if(index1[temp.index] < nums2.length) q.add(new Node(temp.index, nums1[temp.index] + nums2[index1[temp.index]]));
            }
            return result;
        }
        class Node{
            int index;
            int sum;
            public Node(int i, int s){ index = i; sum = s; }
        }
    

Log in to reply
 

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