পাইথনে দুটি অ্যারের উপাদানগুলির 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
heap :=একটি তালিকা উপস্থাপনায় একটি নতুন গাদা
q এর প্রতিটি উপাদানের জন্য, করুন
- যদি elem>=0 হয়, তাহলে
  - আমি পরিসরে (p - 1 এর আকার) থেকে -1 পর্যন্ত, 1 দ্বারা হ্রাস করুন, করুন
    - cd :=elem * p[i]
    - যদি হিপ খালি না হয় এবং হিপের আকার k এবং cd <=heap[0] এর মতো হয়, তাহলে
      - লুপ থেকে বেরিয়ে আসুন
    - গদাতে মান সিডি ঢোকান
    - যদি (হিপ)> k এর দৈর্ঘ্য, তাহলে
      - স্তূপ থেকে ক্ষুদ্রতম আইটেম মুছুন
- অন্যথায়,
  - 0 থেকে p এর আকারের মধ্যে,
    - cd :=elem * p[i]
    - যদি হিপ খালি না হয় এবং হিপের আকার k এবং cd <=heap[0] এর মতো হয়, তাহলে
      - লুপ থেকে বেরিয়ে আসুন
    - গদাতে সিডি ঢোকান
    - যদি (হিপ)> 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