สมมติว่าเราต้องการออกแบบคลาสเพื่อค้นหาองค์ประกอบที่ใหญ่ที่สุดลำดับที่ k ในสตรีม เป็นองค์ประกอบที่ใหญ่ที่สุดลำดับที่ k ในลำดับการจัดเรียง ไม่ใช่องค์ประกอบเฉพาะที่ k
คลาส KthLargest จะมีคอนสตรัคเตอร์ที่ยอมรับจำนวนเต็ม k และจำนวนอาร์เรย์ ซึ่งจะมีองค์ประกอบเริ่มต้นจากสตรีม สำหรับการเรียกใช้เมธอด KthLargest.add แต่ละครั้ง จะส่งคืนองค์ประกอบที่แสดงถึงองค์ประกอบที่ใหญ่ที่สุดลำดับที่ k ในสตรีม
ดังนั้น หากอินพุตเป็น k =3 องค์ประกอบเริ่มต้น =[4,5,8,2] ให้เรียก add(3), add(5), add(10), add(9), add(4) . แล้วผลลัพธ์จะเป็น 4,5,5,8,8 ตามลำดับ
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- กำหนดตัวเริ่มต้น ซึ่งจะใช้เวลา k, nums
- array :=nums
- กำหนดฟังก์ชัน add() นี่จะใช้เวลา val
- แทรก val ที่ส่วนท้ายของอาร์เรย์
- จัดเรียงอาร์เรย์
- ส่งคืนอาร์เรย์[ขนาดของอาร์เรย์ -k]
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
class KthLargest: def __init__(self, k, nums): self.array = nums self.k = k def add(self, val): self.array.append(val) self.array.sort() return self.array[len(self.array)-self.k] ob = KthLargest(3, [4,5,8,2]) print(ob.add(3)) print(ob.add(5)) print(ob.add(10)) print(ob.add(9)) print(ob.add(4))
อินพุต
ob.add(3) ob.add(5) ob.add(10) ob.add(9) ob.add(4)
ผลลัพธ์
4 5 5 8 8
