P199. 查找和最小的 K 对数字

#1

https://algocasts.io/episodes/Z5mz0Qpd

#2

贴上我丑陋的python代码把，我的写法是定下第一行，然后从上往下扫描
博主的是定下左边，从左往右扫描，原理都差不多

    class Solution(object):
    def kSmallestPairs(self, nums1, nums2, k):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :type k: int
        :rtype: List[List[int]]
        """
        if not nums1 and not nums2 or len(nums1) == 0 or len(nums2) == 0: return []
        heap = [(nums1[0] + nums2[y], 0, y) for y in range(len(nums2))]
        heapq.heapify(heap)
        res = []
        
        #边界情况，当k的值大于所有对的数量时，我们要返回所有结果
        if k > len(nums1) * len(nums2): k = len(nums1) * len(nums2)

        for i in range(k):
            val, x, y = heapq.heappop(heap)
            res.append((nums1[x], nums2[y]))
            if x + 1 < len(nums1):
                heapq.heappush(heap, (nums1[x + 1] + nums2[y], x + 1, y))
        return res
1赞