โปรแกรมค้นหาผลิตภัณฑ์ที่ใหญ่ที่สุดลำดับที่ k ขององค์ประกอบสองอาร์เรย์ใน Python

สมมติว่าเราได้รับสองรายการ p และ q ที่มีตัวเลขจำนวนเต็มบางตัว เราต้องคูณค่าทั้งหมดของรายการเหล่านี้และต้องหาค่าที่มากที่สุดเป็นอันดับที่ k จากผลการคูณ

ดังนั้น หากอินพุตเป็น p =[2, 5], q =[6, 8], k =2 ผลลัพธ์จะเป็น 16

ผลการคูณคือ:2 * 6 =12, 2 * 8 =16, 5 * 6 =30, 5 * 8 =40 องค์ประกอบที่ใหญ่เป็นอันดับ 2 คือ (ดัชนีเริ่มจาก 0) คือ 16

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• เรียงลำดับรายการ p
• เรียงลำดับรายการ q
• k :=k + 1
• heap :=ฮีปใหม่ในการแสดงรายการ
• สำหรับแต่ละองค์ประกอบใน q ทำ
  • ถ้าองค์ประกอบ>=0 แล้ว
    • สำหรับ i ในช่วง (ขนาด p - 1 ) ถึง -1, ลดลง 1, do
      • cd :=elem * p[i]
      • หากฮีปไม่ว่างเปล่าและขนาดของฮีปเท่ากับ k และ cd <=heap[0] ดังนั้น
        • ออกมาจากวงจร
      • แทรกค่า cd ลงในฮีป
      • ถ้าความยาวของ (ฮีป)> k แล้ว
        • ลบรายการที่เล็กที่สุดออกจากฮีป
  • มิฉะนั้น
    • สำหรับ i ในช่วง 0 ถึงขนาด p ให้ทำ
      • cd :=elem * p[i]
      • หากฮีปไม่ว่างเปล่าและขนาดของฮีปเท่ากับ k และ cd <=heap[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

ผลลัพธ์

16