पायथन में दो सरणियों के एलिमेंट्स के उत्पाद का k-वां सबसे बड़ा मान ढूंढने का प्रोग्राम

मान लीजिए हमें दो लिस्ट p और q दी गई हैं जिनमें कुछ इंटीजर नंबर हैं। हमें इन लिस्ट के सभी मानों को गुणा करना है और गुणन परिणामों से k-वां सबसे बड़ा मान ढूंढना है।

इसलिए, यदि इनपुट p = [2, 5], q = [6, 8], k = 2 है, तो आउटपुट 16 होगा।

गुणन परिणाम हैं: 2 * 6 = 12, 2 * 8 = 16, 5 * 6 = 30, 5 * 8 = 40। दूसरा सबसे बड़ा एलिमेंट (इंडेक्स 0 से शुरू) 16 है।

समाधान दृष्टिकोण

• दोनों लिस्ट को सॉर्ट करें
• कुशल शीर्ष-k ट्रैकिंग के लिए हीप का उपयोग करें
• पॉजिटिव और नेगेटिव एलिमेंट्स को अलग-अलग संभालें
• हीप के रूट से k-वां सबसे बड़ा मान लौटाएं

उदाहरण कार्यान्वयन

from heapq import heappush, heappop

def solve(p, q, k):
    p = sorted(p)
    q = sorted(q)
    k += 1
    heap = []
    for elem in q:
        if elem >= 0:
            for i in range(len(p) - 1, -1, -1):
                cd = elem * p[i]
                if heap and len(heap) == k and cd <= heap[0]:
                    break
                heappush(heap, cd)
                if len(heap) > k:
                    heappop(heap)
        else:
            for i in range(len(p)):
                cd = elem * p[i]
                if heap and len(heap) == k and cd <= heap[0]:
                    break
                heappush(heap, cd)
                if len(heap) > k:
                    heappop(heap)
    return heap[0]

print(solve([2, 5], [6, 8], 2))

इनपुट

[2, 5], [6, 8], 2

आउटपुट

16