C++で周波数スタックを構築するプログラム

FrequencyStackという1つのスタックを構築したいとします。FrequencyStackには2つの関数があります-

• append（x）、これは値xをスタックに追加またはプッシュします。

• pop（）、これはスタック内で最も頻繁な要素を削除して返します。同じ頻度の要素が複数ある場合は、スタックの最上位に最も近い要素が削除されて返されます。

したがって、入力が7、9、7、9、6、7などの要素を追加するようなものである場合、ポップ操作を4回実行すると、出力はそれぞれ7、9、7、6になります。

これを解決するには、次の手順に従います-

• 1つのマップcntを定義する

• 1つのマップ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