数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会研究
时尚研究
法律研究用 C++ 编写最大频率栈
假设我们想要实现一个名为 FreqStack 的栈，FreqStack 有两个函数 -
push(x)，它会将一个整数 x 栈顶。
pop()，它会移除并返回栈中最频繁出现的元素。如果有多个元素出现频率相同，则移除并返回最靠近栈顶的元素。
因此，如果输入如下，依次压入元素 7、9、7、9、6、7，然后执行四次 pop 操作，则对应的输出应分别为 7、9、7、6。
要解决此问题，我们将按照以下步骤操作 -
定义一个映射 cnt
定义一个映射 sts
maxFreq := 0
定义一个函数 push()，它将接受 x，
(将 cnt[x] 增加 1)
maxFreq := maxFreq 和 cnt[x] 中的最大值
将 x 插入 sts[cnt[x]]
定义一个函数 pop()
maxKey := maxFreq
x := sts[maxKey] 的栈顶元素
从 sts[maxKey] 中删除该元素
如果 sts[maxKey] 的大小为 0，则 -
从 sts 中删除 maxKey
(将 maxFreq 减少 1)
(将 cnt[x] 减少 1)
返回 x
接下来，我们将查看以下实现，以便更好地理解 -
示例
#include <bits/stdc++.h>
using namespace std;
class FreqStack {
public:
unordered_map <int ,int > cnt;
unordered_map <int, stack <int> >sts;
int maxFreq = 0;
FreqStack() {
maxFreq = 0;
cnt.clear();
sts.clear();
}
void push(int x) {
cnt[x]++;
maxFreq = max(maxFreq, cnt[x]);
sts[cnt[x]].push(x);
}
int pop() {
int maxKey = maxFreq;
int x = sts[maxKey].top();
sts[maxKey].pop();
if(sts[maxKey].size() == 0){
sts.erase(maxKey);
maxFreq--;
}
cnt[x]--;
return x;
}
};
main(){
FreqStack ob;
ob.push(7);
ob.push(9);
ob.push(7);
ob.push(9);
ob.push(6);
ob.push(7);
cout << (ob.pop()) << endl;
cout << (ob.pop()) << endl;
cout << (ob.pop()) << endl;
cout << (ob.pop()) << endl;
}输入
push elements 7, 9, 7, 9, 6, 7, then call pop() four times.
输出
7 9 7 6
更新于： 2020 年 6 月 4 日
323 次浏览
广告