在Python中查找K个最大和对的程序

Z时代
2024-01-10
分类：综合

假设我们已经得到两个数字列表，分别是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))