পাইথনে দুটি অ্যারে-এর উপাদানগুলোর গুণফলের 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। ২য় সর্বোচ্চ উপাদান (ইন্ডেক্স ০ থেকে শুরু) হল 16।

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

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