[LeetCode] 895. Maximum Frequency Stack 最大频率栈
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.
这道题让我们实现一种最大频率栈,有入栈和出栈功能,需要每次出栈的都是栈中出现频率最大的数字,若有多个数字的频率相同,那么离栈顶最近的元素先出栈。刚开始看到这道题的时候,博主立马联想到了 [LRU Cache](http://www.cnblogs.com/grandyang/p/4587511.html) 和 [LFU Cache](http://www.cnblogs.com/grandyang/p/6258459.html),想着会不会也需要在迭代器上做文章,但实际是我想多了,虽然同为 Hard 的题目,这道题的解法却要比之前那两道要简单的多。这里只跟数字出现的频率有关,只有在频率相等的情况下才会考虑栈的后入先出的特性,所以一定是需要统计栈中每个数字出现的频率的,我们使用一个 HashMap 来建立每个数字跟其出现次数之间的映射。由于频率相等的数字可能有多个,所以我们必须知道某个特性频率下都有哪些数字,再用一个 HashMap 来建立频率和该频率下所有的数字之间的映射,可以将这些数组放到一个数组或者一个栈中,这里为了简便起见,就使用一个数组了。另外,我们还需要维护一个当前最大频率的变量,可以通过这个值到 HashMap 中快速定位数组的位置。好,一切准备就绪之后就开始解题吧,对于入栈函数 push(),首先需要将x对应的映射值加1,并更新最大频率 mxFreq,然后就是要把x加入当前频率对应的数组中,注意若某个数字出现了3次,那么数字会分别加入频率为 1,2,3 的映射数组中。接下来看出栈函数 pop() 如何实现,由于我们知道当前最大频率 mxFreq,就可以直接去 HashMap 中取出该频率下的所有数字的数组,题目说了若频率相等,取离栈顶最近的元素,这里就是数组末尾的数组,取到之后,要将该数字从数组末尾移除。移除之后,我们要检测一下,若数组此时为空了,说明当前最大频率下之后一个数字,取出之后,最大频率就要自减1,还有不要忘记的就是取出数字的自身的频率值也要自减1,参见代码如下:
解法一:
class FreqStack {
public:
FreqStack() {}
void push(int x) {
mxFreq = max(mxFreq, ++freq[x]);
m[freq[x]].push_back(x);
}
int pop() {
int x = m[mxFreq].back();
m[mxFreq].pop_back();
if (m[freq[x]--].empty()) --mxFreq;
return x;
}
private:
int mxFreq;
unordered_map<int, int> freq;
unordered_map<int, vector<int>> m;
};
我们还可以使用 multimap 来建立频率和数字之间的映射,利用其可重复的特性,那么同一个频率就可以映射多个数字了。同时,由于 multimap 默认是按从小到大排序的,而我们希望按频率从大到小排序,所以加上一个参数使其改变排序方式。在入栈函数中,将x的频率自增1,然后跟x组成 pair 对儿加入 multimap 中。在出栈函数中,由于其是按从大到小排序的,而且后进的排在前面,那么第一个映射对儿就是频率最大且最后加入的数字,将其取出并从 multimap 中移除,并同时将该数字的映射频率值减1即可,参见代码如下:
解法二:
class FreqStack {
public:
FreqStack() {}
void push(int x) {
m.insert({++freq[x], x});
}
int pop() {
int x = m.begin()->second;
m.erase(m.begin());
--freq[x];
return x;
}
private:
unordered_map<int, int> freq;
multimap<int, int, greater_equal<int>> m;
};
Github 同步地址:
https://github.com/grandyang/leetcode/issues/895
参考资料:
https://leetcode.com/problems/maximum-frequency-stack/
https://leetcode.com/problems/maximum-frequency-stack/discuss/163410/C%2B%2BJavaPython-O(1)
[LeetCode All in One 题目讲解汇总(持续更新中...)](https://www.cnblogs.com/grandyang/p/4606334.html)
最新文章
- 使用Auto Layout中的VFL(Visual format language)--代码实现自动布局【转】
- php学习笔记:利用递归实现删除文件目录
- MVC 扩展方法特点
- Linux阵列 RAID详解
- 关于使用 Connect-Busboy 实现文件上传 优化说明
- Qt之进程间通信(IPC)
- opencv 在工业中的应用:模板匹配
- (转)jQuery LigerUI 插件介绍及使用之ligerTree
- 《JavaScript设计模式与开发实践》读书笔记之中介者模式
- Django中使用CKEditor代码高亮显示插件Code Snippet
- Charles手机抓包实用教程
- jieba 库的使用和好玩的词云
- python-day5内置模块time、range、sys、os、shelve、xml、max等
- 数据库的范式,第一、二、三、四、五范式、BC范式
- linux系统centOS7下搭建redis集群中ruby版本过低问题的解决方法
- python爬虫之一:requests库
- Spring-Session实现Session共享入门教程
- How to map Actions to a certain RibbonPage and RibbonGroup using the Application Model or in code
- 一文看尽HashMap
- Hive常见问题汇总
热门文章
- 容器网络插件那么多,博云为什么基于OVS深度自研?
- 坑爹的京东E卡(京东E卡的正确使用方式)
- 微软官方 Github 上的 EF 示例项目 EntityFramework.Docs
- Powershell ExecutionPolicy 执行策略
- Linux安装centos,网络net8模式ping不通www.baidu.com或者ping不通主机
- HashHelper
- vue如何导入外部js文件(es6)
- 大白话说GIT常用操作,常用指令git操作大全
- SAP MM Purchase Order History Category
- 达能依靠Matrikon进行数据存储和分析