পাইথনে K-সবচেয়ে বড় যোগফল খুঁজে পাওয়ার প্রোগ্রাম

ধরুন, আমাদের দুটি সংখ্যার তালিকা দেওয়া হয়েছে যেগুলি হল nums0 এবং nums1, এবং একটি পূর্ণসংখ্যা k৷ আমাদের লক্ষ্য হল k বৃহত্তম যোগফলের জোড়া খুঁজে বের করা যেখানে প্রতিটি জোড়ার সংখ্যা 0-এ একটি পূর্ণসংখ্যা এবং 1-এ আরেকটি পূর্ণসংখ্যা রয়েছে। সব জোড়ার যোগফল ফেরত দিতে হবে।

সুতরাং, যদি ইনপুট 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 :=সংখ্যার আকার 0 − 1, সংখ্যা 1 − 1
পরিদর্শন করেছেন :=একটি নতুন সেট
pq(−(nums0[i] + nums1[j]), i, j)
0 থেকে k রেঞ্জের জন্য, করুন
- 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) পরিদর্শনে অ-শূন্য হয়, তাহলে
  - পরিদর্শনে যোগ করুন(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