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이 아닌 경우
- 0 반환
pq :=새로운 최소 힙
답변 :=0
nums0 및 nums1 목록 정렬
i, j :=nums0 - 1의 크기, nums1 - 1의 크기
방문:=새로운 세트
힙에 푸시 pq(−(nums0[i] + nums1[j]) , i, j)
범위 0에서 k에 있는 i에 대해 수행
- sum, i, j :=힙 pq에서 팝
- x :=nums0[i − 1] + nums1[j]
- 방문에서 (i − 1, j)가 0이 아닌 경우
  - add(i − 1, j) 방문
  - 힙에 푸시 pq(−x, i − 1, j)
- y :=nums0[i] + nums1[j − 1]
- 방문에서 not (i, j − 1)이 0이 아닌 경우
  - add(i, j − 1) 방문
  - 힙에 푸시 pq( −y, i, j − 1)
- ans :=ans + −sum
반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

파이썬

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