Giả sử ta muốn thiết kế một lớp để tìm phần tử K-th lớn nhất trong một luồng dữ liệu. Đây là phần tử K-th lớn nhất theo thứ tự đã sắp xếp, không phải phần tử K-th khác biệt.
Lớp KthLargest sẽ có hàm khởi tạo nhận một số nguyên k và một mảng nums, chứa các phần tử ban đầu từ luồng. Với mỗi lần gọi phương thức KthLargest.add, sẽ trả về phần tử đại diện cho K-th lớn nhất trong luồng.
Ví dụ, nếu đầu vào là k = 3, các phần tử ban đầu = [4,5,8,2], sau đó gọi add(3), add(5), add(10), add(9), add(4)., thì đầu ra sẽ là 4,5,5,8,8 lần lượt.
Để giải quyết, ta thực hiện các bước sau:
- Định nghĩa hàm khởi tạo, nhận k, nums
- array := nums
- Định nghĩa hàm add(). Nhận val
- Thêm val vào cuối array
- Sắp xếp array
- Trả về array[kích thước array - k]
Hãy xem triển khai sau để hiểu rõ hơn:
Ví dụ
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))
Đầu vào
ob.add(3) ob.add(5) ob.add(10) ob.add(9) ob.add(4)
Đầu ra
4 5 5 8 8