โปรแกรมหาคู่ผลรวมที่ใหญ่ที่สุด K ใน Python

สมมติว่าเราได้รับรายการตัวเลขสองรายการคือ 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

• เข้าชมแล้ว :=ชุดใหม่

• ดันเข้าไปใน heap pq(−(nums0[i] + nums1[j]) , i, j)

• สำหรับฉันอยู่ในช่วง 0 ถึง k ทำ

  • sum, i, j :=ป๊อปจาก heap 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) ในการเยี่ยมชมจะไม่เท่ากับศูนย์ ดังนั้น

    • เพิ่ม (i, j -1) เยี่ยมชม

    • ดันเข้าไปใน heap 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

ผลลัพธ์

38