สมมติว่าเราต้องการสร้างหนึ่งสแต็กที่เรียกว่า FrequencyStack ของเรา FrequencyStack มีสองหน้าที่ -
-
append(x) ซึ่งจะต่อท้ายหรือส่งค่า x ลงบนสแต็ก
-
pop() สิ่งนี้จะลบและส่งคืนองค์ประกอบที่บ่อยที่สุดในสแต็ก หากมีองค์ประกอบมากกว่าหนึ่งองค์ประกอบที่มีความถี่เท่ากัน องค์ประกอบที่ใกล้กับส่วนบนสุดของสแต็กจะถูกลบออกและส่งคืน
ดังนั้น หากอินพุตเป็นเหมือนผนวกองค์ประกอบบางอย่าง เช่น 7, 9, 7, 9, 6, 7 จากนั้นดำเนินการป๊อปอัปสี่ครั้ง ผลลัพธ์จะเป็น 7,9,7,6 ตามลำดับ
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดหนึ่งแผนที่ cnt
-
กำหนดหนึ่ง 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 แล้ว −
-
ลบ maxKey ออกจาก sts
-
(ลดความถี่สูงสุดลง 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
