用 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 次浏览

开启您的职业生涯

完成课程，获得认证

开始
广告