1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
|
class : def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]: m, n = len(nums1), len(nums2) if m == 0 or n == 0: return [] res, heap, seen = [], [(nums1[0] + nums2[0], 0, 0)], {(0, 0)} for _ in range(k): if not heap: return res v, i, j = heapq.heappop(heap) res.append((nums1[i], nums2[j])) if i < m - 1 and (i + 1, j) not in seen: seen.add((i + 1, j)) heapq.heappush(heap, (nums1[i + 1] + nums2[j], i + 1, j)) if j < n - 1 and (i, j + 1) not in seen: seen.add((i, j + 1)) heapq.heappush(heap, (nums1[i] + nums2[j + 1], i, j + 1)) return res
|
近期评论