Python solution using heapq


  • 0
    C
    import heapq
    class Solution(object):
        def kSmallestPairs(self, nums1, nums2, k):
            if len(nums1)*len(nums2) <= k:
                return [[i, j] for i in nums1 for j in nums2]
            hp = [[n + nums2[0], n, 0] for n in nums1]
            res = []
            for i in range(k):
                psum, n, ind = hp[0]
                res.append([n, psum - n])
                if ind + 1 == len(nums2):
                    heapq.heappop(hp)
                else:
                    heapq.heapreplace(hp, [n + nums2[ind+1], n, ind+1])
            return res
    

  • 0
    P

    why you have

     if len(nums1)*len(nums2) <= k:
                return [[i, j] for i in nums1 for j in nums2]
    

    how do you know the itration of i, j for all elements in num1 and num2 will produce all pair sums in right order


  • 0
    P

    I think your code fail this case:

    num1 = [2,4,6]
    num2 =[1,7,11]
    k = 10
    its output is
    [[2,1],[2,7],[2,11],[4,1],[4,7],[4,11],[6,1],[6,7],[6,11]]
    while the correct order should be
    [[2,1],[4,1],[6,1],[2,7],[4,7],[2,11],[6,7],[4,11],[6,11]]

    but it get passed the OJ.


  • 0
    F

    @pennlio I don't think the problem seeks the first k pairs in a sorted order.


Log in to reply
 

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