Giả sử, chúng ta được cung cấp hai danh sách các số là nums0 và nums1 và một số nguyên k. Mục tiêu của chúng ta là tìm k cặp tổng lớn nhất trong đó mỗi cặp chứa một số nguyên ở nums0 và một số nguyên khác ở nums1. Tổng của tất cả các cặp phải được trả lại.
Vì vậy, nếu đầu vào là nums1 =[8, 6, 12], nums2 =[4, 6, 8], k =2, thì đầu ra sẽ là 38. Chúng ta có các cặp lớn nhất này [12, 8] và [ 12, 6].
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
nếu k> len (nums0) * len (nums1) khác 0, thì
-
trả về 0
-
-
pq:=a min heap mới
-
ans:=0
-
sắp xếp danh sách nums0 và nums1
-
i, j:=kích thước của nums0 - 1, kích thước của nums1 - 1
-
đã ghé thăm:=một tập hợp mới
-
đẩy vào heap pq (- (nums0 [i] + nums1 [j]), i, j)
-
đối với tôi trong phạm vi từ 0 đến k, thực hiện
-
sum, i, j:=pop from heap pq
-
x:=nums0 [i - 1] + nums1 [j]
-
nếu không (i - 1, j) được truy cập là khác 0, thì
-
thêm (i - 1, j) vào đã truy cập
-
đẩy vào heap pq (−x, i - 1, j)
-
-
y:=nums0 [i] + nums1 [j - 1]
-
nếu không (i, j - 1) trong được truy cập là khác 0, thì
-
thêm (i, j - 1) vào đã truy cập
-
đẩy vào heap pq (−y, i, j - 1)
-
-
ans:=ans + −sum
-
-
trả lại ans
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Python
from heapq import heappush, heappop class Solution: def solve(self, nums0, nums1, k): if k > len(nums0) * len(nums1): return 0 pq = [] ans = 0 nums0.sort(), nums1.sort() i, j = len(nums0) − 1, len(nums1) − 1 visited = set() heappush(pq, (−(nums0[i] + nums1[j]), i, j)) for _ in range(k): sum, i, j = heappop(pq) x = nums0[i − 1] + nums1[j] if not (i − 1, j) in visited: visited.add((i − 1, j)) heappush(pq, (−x, i − 1, j)) y = nums0[i] + nums1[j − 1] if not (i, j − 1) in visited: visited.add((i, j − 1)) heappush(pq, (−y, i, j − 1)) ans += −sum return ans ob = Solution() print(ob.solve([8, 6, 12], [4, 6, 8], 2))
Đầu vào
[8, 6, 12],[4, 6, 8],2
Đầu ra
38