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

假设我们已经有两个数字列表nums0和nums1以及一个整数k。我们的目标是找出包含nums0中一个整数和nums1中另一个整数的k个最大和的对。需要返回所有对的总和。

因此，如果输入为nums1 = [8, 6, 12]，nums2 = [4, 6, 8]，k = 2，则输出将是38。我们有这些最大的对[12, 8]和[12, 6]。

为了解决这个问题，我们将遵循以下步骤−

如果k > len(nums0) * len(nums1)为非零，则
- 返回0
pq：一个新的最小堆
ans：0
对列表nums0和nums1进行排序
i，j：nums0和nums1的大小−1
visited：一个新的集合
将(−(nums0[i] + nums1[j])，i，j)推入堆pq
对于范围为0到k的i，执行以下操作
- sum，i，j：从堆pq弹出
- x：等于nums0[i−1] + nums1[j]
- 如果未访问过(i−1，j)为非零，则
  - 将(i−1，j)添加到visited中
  - 将(−x，i−1，j)推入堆pq
- y：等于nums0[i] + nums1[j−1]
- 如果未访问过(i，j−1)为非零，则
  - 将(i，j−1)添加到visited中
  - 将(−y，i，j−1)推入堆pq
- 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))