P199. 查找和最小的 K 对数字
贴上我丑陋的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赞