โปรแกรมค้นหาองค์ประกอบที่เล็กที่สุดลำดับ k ในเวลาเชิงเส้นด้วย Python

ปัญหา

ให้รายการตัวเลข nums และค่า k ให้หาองค์ประกอบที่เล็กที่สุดลำดับ k (นับจาก 0) ในรายการ โดยต้องแก้ปัญหาในเวลา O(n) เฉลี่ย

ตัวอย่าง

Input: nums = [6, 4, 9, 3, 1], k = 2
Output: 4
# หลังเรียงลำดับ: [1, 3, 4, 6, 9] -> องค์ประกอบลำดับที่ 2 คือ 4

อัลกอริทึม: ใช้ Max Heap ขนาด k+1

1. สร้าง Max Heap ว่าง
2. ใส่ k+1 องค์ประกอบแรกลงใน Heap (ใช้ค่าลบเพราะ Python มี min-heap เท่านั้น)
3. สำหรับองค์ประกอบที่เหลือ:
   • ถ้าค่านั้น น้อยกว่า ค่าสูงสุดใน Heap (คือ -maxHeap[0]) ให้ลบค่าสูงสุดออกและใส่ค่าใหม่เข้าไป
4. คืนค่า -maxHeap[0] ซึ่งเป็นคำตอบ

การทำงาน

• Heap จะเก็บ k+1 ค่าที่เล็กที่สุดที่เจอจนถึงตอนนั้น
• รากของ Max Heap (ค่ามากที่สุดใน Heap) จะเป็นคำตอบเมื่อจบการวนลูป
• ความซับซ้อนเวลา: O(n log k) ≈ O(n) เมื่อ k คงที่

ตัวอย่างโค้ด

from heapq import heappop, heappush

def solve(nums, k):
    maxHeap = []
    # ใส่ k+1 ตัวแรก
    for i in range(k + 1):
        heappush(maxHeap, -nums[i])
    
    # ประมวลผลตัวที่เหลือ
    for i in range(k + 1, len(nums)):
        if nums[i] < -maxHeap[0]:
            heappop(maxHeap)
            heappush(maxHeap, -nums[i])
    
    return -maxHeap[0]

nums = [6, 4, 9, 3, 1]
k = 2
print(solve(nums, k))  # Output: 4

อินพุต / เอาต์พุต

Input: [6, 4, 9, 3, 1], 2
Output: 4