JAVA 5ms 99.1%, a relatively simple solution with O(k * (min_length of nums1, nums2)) worst case


  • 0
    O

    It is not a better solution than using a priority queue with O(k * log(k)) time complexity. However this solution looks simple. The idea is that we need to think about which pair will give the smallest sum to be added. To find that pair, we need to maintain an int[] to record the pairs that have already been added. For example, an int[] = { 3, 0, 0 } means the first number from nums1 has been paired with the 4th number (index = 3) from nums2 and this pair has been added. Now the question is what will be the next pair? It is easy to realize that it can either be 1st number from nums1 with 5th number from nums2 or 2nd number from nums1 with 1st number from nums2. But we don't need to think about the 3rd number from nums1 yet because it will be large than the 2nd number from nums1 anyway. So we use "start" and "end" to record the range we need to search in nums1, which can reduce our search range.

    public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<int[]> res = new ArrayList();
        if (nums1 == null || nums2 == null) { return res; }
        int n1 = nums1.length, n2 = nums2.length;
        if (n1 == 0 || n2 == 0) { return res; }
        int[] index = new int[n1];
        int start = 0, end = 0;
        for (int i = 0; i < k; i++) {
            int minSum = Integer.MAX_VALUE, next1 = 0, next2 = 0;
            for (int j = start; j <= end; j++) {
                if (nums1[j] + nums2[index[j]] < minSum) {
                    next1 = j;
                    next2 = index[j];
                    minSum = nums1[j] + nums2[index[j]];
                }
            }
            res.add(new int[]{nums1[next1], nums2[next2]});
            index[next1]++;
            if (index[start] == n2 && ++start == n1) {
                return res;
            }
            if (end < n1 - 1 && index[end] > index[end + 1]) {
                end++;
            }
        }
        return res;
    }

Log in to reply
 

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