Problem
Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.
Your KthLargest
class will have a constructor which accepts an integer k
and an integer array nums
, which contains initial elements from the stream. For each call to the method KthLargest.add
, return the element representing the kth largest element in the stream.
Example:
int k = 3; int[] arr = [4,5,8,2]; KthLargest kthLargest = new KthLargest(3, arr); kthLargest.add(3); // returns 4 kthLargest.add(5); // returns 5 kthLargest.add(10); // returns 5 kthLargest.add(9); // returns 8 kthLargest.add(4); // returns 8
Note:
You may assume that nums
‘ length ≥ k-1
and k
≥ 1.
Solution: BST / Min Heap
Time complexity: O(nlogk)
Space complexity: O(k)
C++ / BST
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua // Running time: 32 ms class KthLargest { public: KthLargest(int k, vector<int> nums): k_(k) { for (int num : nums) add(num); } int add(int val) { s_.insert(val); if (s_.size() > k_) s_.erase(s_.begin()); return *s_.begin(); } private: const int k_; multiset<int> s_; }; |
C++ / Min Heap
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua // Running time: 28 ms class KthLargest { public: KthLargest(int k, vector<int> nums): k_(k) { for (int num : nums) add(num); } int add(int val) { s_.push(val); if (s_.size() > k_) s_.pop(); return s_.top(); } private: const int k_; priority_queue<int, vector<int>, greater<int>> s_; // min heap }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment