Problem
Implement FreqStack
, a class which simulates the operation of a stack-like data structure.
FreqStack
has two functions:
push(int x)
, which pushes an integerx
onto the stack.pop()
, which removes and returns the most frequent element in the stack.- If there is a tie for most frequent element, the element closest to the top of the stack is removed and returned.
Example 1:
Input: ["FreqStack","push","push","push","push","push","push","pop","pop","pop","pop"], [[],[5],[7],[5],[7],[4],[5],[],[],[],[]] Output: [null,null,null,null,null,null,null,5,7,5,4] Explanation: After making six .push operations, the stack is [5,7,5,7,4,5] from bottom to top. Then: pop() -> returns 5, as 5 is the most frequent. The stack becomes [5,7,5,7,4]. pop() -> returns 7, as 5 and 7 is the most frequent, but 7 is closest to the top. The stack becomes [5,7,5,4]. pop() -> returns 5. The stack becomes [5,7,4]. pop() -> returns 4. The stack becomes [5,7].
Note:
- Calls to
FreqStack.push(int x)
will be such that0 <= x <= 10^9
. - It is guaranteed that
FreqStack.pop()
won’t be called if the stack has zero elements. - The total number of
FreqStack.push
calls will not exceed10000
in a single test case. - The total number of
FreqStack.pop
calls will not exceed10000
in a single test case. - The total number of
FreqStack.push
andFreqStack.pop
calls will not exceed150000
across all test cases.
Solution 1: Buckets
We have n stacks. The i-th stack has the of elements with freq i when pushed.
We keep tracking the freq of each element.
push(x): stacks[++freq(x)].push(x) # inc x’s freq and push it onto freq-th stack
pop(): x = stacks[max_freq].pop(), –freq(x); # pop element x from the max_freq stack and dec it’s freq.
Time complexity: O(1) push / pop
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
// Author: Huahua // Running time: 144 ms class FreqStack { public: FreqStack() {} void push(int x) { auto it = freq_.find(x); if (it == freq_.end()) it = freq_.emplace(x, 0).first; int freq = ++it->second; if (stacks_.size() < freq) stacks_.push_back({}); stacks_[freq - 1].push(x); } int pop() { int x = stacks_.back().top(); stacks_.back().pop(); if (stacks_.back().empty()) stacks_.pop_back(); auto it = freq_.find(x); if (!(--it->second)) freq_.erase(it); return x; } private: vector<stack<int>> stacks_; unordered_map<int, int> freq_; }; |
Solution2: Priority Queue
Use a max heap with key: (freq, seq), the max freq and closest to the top of stack element will be extracted first.
Time complexity: O(logn)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// Author: Huahua // Running time: 132 ms class FreqStack { public: FreqStack() {} void push(int x) { int key = (++f_[x] << 16) | (++seq_); q_.emplace(key, x); } int pop() { int x = q_.top().second; q_.pop(); if (--f_[x] == 0) f_.erase(x); return x; } private: int seq_ = 0; unordered_map<int, int> f_; // {x -> freq} priority_queue<pair<int, int>> q_; // {freq | seq_, x} }; |
Related Problems
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment