假设我们已经得到两个数字列表,分别是nums0和nums1,以及一个整数k。我们的目标是找到k个最大的和对,其中每个对在nums0中包含一个整数,在nums1中包含另一个整数。所有对的总和必须返回。
因此,如果输入像nums1 = [8,6,12],nums2 = [4,6,8],k = 2,则输出将为38。我们有这些最大的对[12,8]和[ 12、6]。
为了解决这个问题,我们将遵循以下步骤-
如果k> len(nums0)* len(nums1)不为零,则
返回0
pq:=一个新的最小堆
回答:= 0
对列表nums0和nums1进行排序
i,j:= nums0-1的大小,nums1-1-1的大小
参观了:=一套新的
推入堆pq(-(nums0 [i] + nums1 [j]),i,j)
对于0到k范围内的i,执行
将(i,j − 1)添加到访问
推入堆pq(-y,i,j-1)
将(i − 1,j)添加到已访问
推入堆pq(-x,i-1,j)
总和,i,j:=从堆pq弹出
x:= nums0 [i − 1] + nums1 [j]
如果访问的不是(i − 1,j)不为零,则
y:= nums0 [i] + nums1 [j − 1]
如果访问的不是(i,j − 1)为非零,则
ans:= ans + −sum
返回ans
让我们看下面的实现以更好地理解-
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))
[8, 6, 12],[4, 6, 8],2输出结果
38