資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++實現頻率棧程式
假設我們要構建一個名為FrequencyStack的棧，我們的FrequencyStack有兩個函式：
append(x)：將值x新增到棧頂。
pop()：移除並返回棧中最頻繁的元素。如果有多個元素具有相同的頻率，則移除並返回最靠近棧頂的元素。
例如，如果輸入是依次新增元素7, 9, 7, 9, 6, 7，然後執行四次pop操作，則輸出將分別為7, 9, 7, 6。
為了解決這個問題，我們將遵循以下步驟：
定義一個map cnt
定義一個map sts
maxFreq := 0
定義一個函式append()，它將接收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 append(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.append(7);
ob.append(9);
ob.append(7);
ob.append(9);
ob.append(6);
ob.append(7);
cout << (ob.pop()) << endl;
cout << (ob.pop()) << endl;
cout << (ob.pop()) << endl;
cout << (ob.pop()) << endl;
}輸入
ob.append(7); ob.append(9); ob.append(7); ob.append(9); ob.append(6); ob.append(7); cout << (ob.pop()) << endl; cout << (ob.pop()) << endl; cout << (ob.pop()) << endl; cout << (ob.pop()) << endl;
輸出
7 9 7 6
更新於：2020-12-26
瀏覽量：112
廣告