用 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 次瀏覽

開啟您的職業生涯

完成課程，獲得認證

開始
廣告