กองความถี่สูงสุดใน 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.

ผลลัพธ์

7
9
7
6