Problem
实现 FreqStack
,模拟类似栈的数据结构的操作的一个类。
FreqStack
有两个函数:
-
push(int x)
,将整数x
推入栈中。 -
pop()
,它移除并返回栈中出现最频繁的元素。- 如果最频繁的元素不只一个,则移除并返回最接近栈顶的元素。
示例:
输入:
["FreqStack","push","push","push","push","push","push","pop","pop","pop","pop"],
[[],[5],[7],[5],[7],[4],[5],[],[],[],[]]
输出:[null,null,null,null,null,null,null,5,7,5,4]
解释:
执行六次 .push 操作后,栈自底向上为 [5,7,5,7,4,5]。然后:
pop() -> 返回 5,因为 5 是出现频率最高的。
栈变成 [5,7,5,7,4]。
pop() -> 返回 7,因为 5 和 7 都是频率最高的,但 7 最接近栈顶。
栈变成 [5,7,5,4]。
pop() -> 返回 5 。
栈变成 [5,7,4]。
pop() -> 返回 4 。
栈变成 [5,7]。
Solution
这道题目我使用了两个哈希表:
Freq
用来统计数字出现的次数: integer
->unsigned
FreqStack
用来统计出现次数所对应的栈:unsigned
->stack<int>
主要的解法是为每次出现第几次的元素建一个栈,比如
1,3,4,5,1,1,
那么1,3,4,5
就会在FreqStack[1]
上因为他们的出现次数为1
而第二次出现的1
就会压入FreqStack[2]
,第三次出现的1
会出现在FreqStack[3]
,以此类推。
在Freq
哈希表的辅助下,判断出现次数会相当容易。AC代码如下
class FreqStack {
public:
void push(int x) {
Freq[x]++;
maxfreq = max(Freq[x], maxfreq);
FreqStack[Freq[x]].push(x);
}
int pop() {
int x = FreqStack[maxfreq].top();
FreqStack[maxfreq].pop();
if(FreqStack[Freq[x]].empty())
maxfreq--;
Freq[x]--;
return x;
}
private:
unordered_map<int, unsigned> Freq;
unordered_map<unsigned, stack<int>> FreqStack;
unsigned maxfreq = 0;
};