กำหนดลิสต์สองลิสต์ p และ q คูณทุกค่าจากทั้งสองลิสต์ แล้วหาค่าอันดับ k (0-indexed) จากค่าที่มากไปน้อย
ตัวอย่าง
อินพุต: p = [2, 5], q = [6, 8], k = 2 → เอาต์พุต: 16
- ผลคูณทั้งหมด: 2×6=12, 2×8=16, 5×6=30, 5×8=40
- เรียงลำดับมากไปน้อย: 40, 30, 16, 12
- อันดับ 2 (0-indexed) = 16
วิธีแก้ปัญหา
- เรียงลำดับทั้งสองลิสต์
- ใช้ Min-Heap ขนาด
k+1เก็บค่าสูงสุดk+1ค่า - วนลูปคูณค่า โดยใช้ข้อเท็จจริงว่าลิสต์เรียงแล้วเพื่อ prune การคำนวณ
- คืนค่า
heap[0](ค่าน้อยที่สุดใน heap = อันดับ k)
ตัวอย่างโค้ด
from heapq import heappush, heappop
def solve(p, q, k):
p = sorted(p)
q = sorted(q)
k += 1 # ใช้ k+1 เพราะ 0-indexed
heap = []
for elem in q:
if elem >= 0:
# คูณจากค่ามากไปน้อยของ p
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:
# elem ติดลบ คูณจากค่าน้อยไปมากของ p
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))อินพุต / เอาต์พุต
Input: [2, 5], [6, 8], 2 Output: 16
หลักการ: ใช้ Heap ขนาดคงที่ (k+1) เพื่อเก็บค่าสูงสุด k+1 ค่า โดยไม่ต้องคำนวณผลคูณทั้งหมด (O(n²)) ลดความซับซ้อนเหลือ O(n log k)
