Kth Largest Element in a Stream ใน Python: หาค่าที่ K มากที่สุดในสตรีม

ออกแบบคลาส KthLargest หาค่าที่ k-th largest ในสตรีมตัวเลข (เรียงจากมากไปน้อย ไม่นับ distinct) Constructor รับ k และอาร์เรย์เริ่มต้น nums เมธอด add(val) คืนค่า k-th largest ปัจจุบัน

ตัวอย่าง

k=3, nums=[4,5,8,2] → add(3)→4, add(5)→5, add(10)→5, add(9)→8, add(4)→8

ขั้นตอนการแก้ปัญหา (Min-Heap แบบง่าย)

1. เก็บตัวเลขทั้งหมดในลิสต์
2. เมธอด add: เพิ่มค่า, เรียงลำดับ, คืน array[-k]
3. หมายเหตุ: วิธีนี้ O(n log n) ต่อการเพิ่ม สำหรับประสิทธิภาพดีกว่าควรใช้ Min-Heap ขนาด k

การติดตั้งใน Python (แบบเรียงลำดับ)

class KthLargest:
    def __init__(self, k, nums):
        self.k = k
        self.array = sorted(nums)
    def add(self, val):
        import bisect
        bisect.insort(self.array, val)
        return self.array[-self.k]

ob = KthLargest(3, [4,5,8,2])
print(ob.add(3))   # 4
print(ob.add(5))   # 5
print(ob.add(10))  # 5
print(ob.add(9))   # 8
print(ob.add(4))   # 8

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

Input: add(3), add(5), add(10), add(9), add(4)
Output: 4, 5, 5, 8, 8