703.Kth Largest Element in a Stream === ###### tags: `Easy`,`Tree`,`Heap` [703. Kth Largest Element in a Stream](https://leetcode.com/problems/kth-largest-element-in-a-stream/) ### 題目描述 Design a class to find the k^th^ largest element in a stream. Note that it is the k^th^ largest element in the sorted order, not the k^th^ distinct element. Implement `KthLargest` class: * `KthLargest(int k, int[] nums)` Initializes the object with the integer `k` and the stream of integers `nums`. * `int add(int val)` Appends the integer `val` to the stream and returns the element representing the k^th^ largest element in the stream. ### 範例 **Example 1:** ``` Input ["KthLargest", "add", "add", "add", "add", "add"] [[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]] Output [null, 4, 5, 5, 8, 8] Explanation KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]); kthLargest.add(3); // return 4 kthLargest.add(5); // return 5 kthLargest.add(10); // return 5 kthLargest.add(9); // return 8 kthLargest.add(4); // return 8 ``` **Constraints**: * 1 <= `k` <= 10^4^ * 0 <= `nums.length` <= 10^4^ * -10^4^ <= `nums[i]` <= 10^4^ * -10^4^ <= `val` <= 10^4^ * At most 10^4^ calls will be made to `add`. * It is guaranteed that there will be at least `k` elements in the array when you search for the k^th^ element. ### 解答 #### Python ```python= class KthLargest: def __init__(self, k: int, nums: List[int]): self.k = k self.heap = [] for num in nums: self.add(num) def add(self, val: int) -> int: if len(self.heap) < self.k: heapq.heappush(self.heap, val) elif val > self.heap[0]: heapq.heapreplace(self.heap, val) return self.heap[0] ``` > [name=Yen-Chi Chen][time=Tue, May 23, 2023] ```python= class KthLargest: def __init__(self, k: int, nums: List[int]): self.k = k self.heap = nums heapq.heapify(self.heap) while len(self.heap) > self.k: heapq.heappop(self.heap) def add(self, val: int) -> int: heapq.heappush(self.heap, val) if len(self.heap) > self.k: heapq.heappop(self.heap) return self.heap[0] ``` > [name=Ron Chen][time=Tue, May 23, 2023] #### Javascript ```javascript= class KthLargest { constructor(k, nums) { this.k = k; this.nums = nums; } add(val) { this.nums.push(val); this.nums.sort((a, b) => b - a); return this.nums[this.k - 1]; } } ``` > 用sort也會過ㄏㄏ > [name=Marsgoat][time=Tue, May 23, 2023] ```javascript= class KthLargest { constructor(k, nums) { this.k = k; this.minHeap = new MinHeap(); for (const num of nums) { this.add(num); } } add(val) { this.minHeap.push(val); if (this.minHeap.size() > this.k) { this.minHeap.pop(); } return this.minHeap.top(); } } ``` > minHeap就不貼了,我直接讓chatGPT把我之前的maxHeap直接改寫成minHeap > [name=Marsgoat][time=Tue, May 23, 2023] #### C++ ``` cpp= class KthLargest { public: multiset<int> bst; int k; vector<int> nums; KthLargest(int k, vector<int>& nums) { this->k = k; for (int x : nums) { bst.insert(x); } } int add(int val) { bst.insert(val); auto it = bst.end(); advance(it, -k); return *it; } }; ``` > [name=Jerry Wu][time=True, May23, 2023] ### Reference [回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)