資料結構
網路
關係型資料庫管理系統 (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 次瀏覽
廣告