पायथन में K-सबसे बड़े योग वाले जोड़े ज्ञात करने का प्रोग्राम

मान लीजिए हमें दो संख्याओं की सूचियाँ 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 := मिन हीप, ans := 0
nums0, nums1 को सॉर्ट करें
i, j := len(nums0)-1, len(nums1)-1
visited := सेट, heappush(pq, (-(nums0[i]+nums1[j]), i, j))
k बार दोहराएं:
- sum, i, j := heappop(pq)
- x = nums0[i-1]+nums1[j], यदि (i-1,j) विज़िटेड नहीं तो डालें
- y = nums0[i]+nums1[j-1], यदि (i,j-1) विज़िटेड नहीं तो डालें
- ans += -sum
ans वापस करें

उदाहरण

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 (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
        return ans

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

इनपुट

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