在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