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과 같으면 -

  • 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