在Python中查找K个最大和对的程序
假设我们已经得到两个数字列表，分别是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
让我们看下面的实现以更好地理解-
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))输入值
[8, 6, 12],[4, 6, 8],2输出结果
38