পাইথনে Kটি সর্বোচ্চ যোগফলযুক্ত জোড়া নির্ণয়

দুটি সংখ্যার তালিকা nums0 এবং nums1 এবং একটি পূর্ণসংখ্যা k দেওয়া আছে। nums0 থেকে একটি এবং nums1 থেকে একটি সংখ্যা নিয়ে kটি সর্বোচ্চ যোগফলযুক্ত জোড়া বের করতে হবে এবং তাদের মোট যোগফল ফেরত দিতে হবে।

উদাহরণ: nums1 = [8, 6, 12], nums2 = [4, 6, 8], k = 2 হলে আউটপুট ৩৮, কারণ সর্বোচ্চ জোড়াগুলো [12,8] এবং [12,6]।

সমাধানের ধাপসমূহ

যদি k > len(nums0)*len(nums1) হয় তবে 0 ফেরত দিন
মিন হিপ (pq) এবং ভিজিটেড সেট ব্যবহার করুন
দুই তালিকা সর্ট করুন এবং শেষ ইন্ডেক্স থেকে শুরু করুন
k বার হিপ থেকে সর্বোচ্চ যোগফল বের করে(ans += -sum) এবং নতুন প্রার্থী পুশ করুন
m infine ফেরত দিন

উদাহরণ কোড

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_val, i, j = heappop(pq)
            x = nums0[i - 1] + nums1[j]
            if (i - 1, j) not in visited:
                visited.add((i - 1, j))
                heappush(pq, (-x, i - 1, j))
            y = nums0[i] + nums1[j - 1]
            if (i, j - 1) not in visited:
                visited.add((i, j - 1))
                heappush(pq, (-y, i, j - 1))
            ans += -sum_val
        return ans

ob = Solution()
print(ob.solve([8, 6, 12], [4, 6, 8], 2))

ইনপুট

[8, 6, 12],[4, 6, 8],2