PythonでK最大の合計ペアを見つけるプログラム

nums0とnums1の2つの数値リストと、整数kが提供されているとします。私たちの目標は、各ペアにnums0に1つの整数が含まれ、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 − 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）がゼロ以外の場合、

    • 訪問したものに（i − 1、j）を追加

    • ヒープにプッシュpq（−x、i − 1、j）

  • y：=nums0 [i] + nums1 [j − 1]

  • 訪問先の（i、j − 1）がゼロ以外の場合、

    • add（i、j − 1）tovisited

    • ヒープにプッシュpq（−y、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