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.
classKthLargest{private:int_k;multiset<int>s;public:KthLargest(intk,vector<int>&nums){for(intnum:nums){s.insert(num);if(s.size()>k)s.erase(s.begin());}_k=k;}intadd(intval){s.insert(val);if(s.size()>_k)s.erase(s.begin());return*s.begin();}};/** * Your KthLargest object will be instantiated and called as such: * KthLargest* obj = new KthLargest(k, nums); * int param_1 = obj->add(val); */
classKthLargest{private:int_k;priority_queue<int,vector<int>,greater<int>>q;public:KthLargest(intk,vector<int>&nums){for(intnum:nums){q.push(num);if(q.size()>k)q.pop();}this->_k=k;}intadd(intval){q.push(val);if(q.size()>_k)q.pop();returnq.top();}};/** * Your KthLargest object will be instantiated and called as such: * KthLargest* obj = new KthLargest(k, nums); * int param_1 = obj->add(val); */
Time complexity: for initializing elements in the heap, and for each insertion operation;