กองความถี่สูงสุดใน C ++

สมมติว่าเราต้องการใช้หนึ่งสแต็คที่เรียกว่า FreqStack FreqStack ของเรามีสองหน้าที่ -

push(x) สิ่งนี้จะผลักจำนวนเต็ม x ลงบนสแต็ก
pop() สิ่งนี้จะลบและส่งคืนองค์ประกอบที่บ่อยที่สุดในสแต็ก หากมีองค์ประกอบมากกว่าหนึ่งรายการที่มีความถี่เท่ากัน องค์ประกอบที่ใกล้กับด้านบนของสแต็กที่สุดจะถูกลบออกและส่งคืน

ดังนั้น หากอินพุตเป็นเหมือนผลักองค์ประกอบบางอย่าง เช่น 7, 9, 7, 9, 6, 7 จากนั้นดำเนินการป๊อปอัปสี่ครั้ง ผลลัพธ์จะเป็น 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 แล้ว −
- ลบ 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 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.

ผลลัพธ์