पायथन में दो सरणियों के तत्वों के 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 है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

सूची क्रमित करें p
सूची को क्रमित करें q
k :=k + 1
ढेर:=सूची प्रतिनिधित्व में एक नया ढेर
क्यू में प्रत्येक तत्व के लिए, करें
- यदि तत्व>=0, तो
  - i रेंज में (p-1 का आकार) से -1 तक, 1 से घटाएं
    - सीडी:=elem * p[i]
    - यदि ढेर खाली नहीं है और ढेर का आकार k और cd <=ढेर [0] के समान है, तो
      - लूप से बाहर आएं
    - मूल्य सीडी को ढेर में डालें
    - यदि लंबाई (ढेर)> k, तो
      - ढेर से छोटी से छोटी वस्तु को हटाएं
- अन्यथा,
  - i के लिए 0 से लेकर p के आकार तक के लिए, करें
    - सीडी:=elem * p[i]
    - यदि ढेर खाली नहीं है और ढेर का आकार k और cd <=ढेर [0] के समान है, तो
      - लूप से बाहर आएं
    - cd को हीप में डालें
    - यदि (ढेर)> k की लंबाई शून्य नहीं है, तो
      - लूप से सबसे छोटा आइटम हटाएं
रिटर्न हीप[0]

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

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