C ++中的最大频率堆栈

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们要实现一个名为FreqStack的堆栈，我们的FreqStack具有两个功能-

  • push(x)，这会将整数x压入堆栈。

  • pop()，这将删除并返回堆栈中最频繁的元素。如果有多个具有相同频率的元素，那么最接近堆栈顶部的元素将被删除并返回。

因此，如果输入像推7、9、7、9、6、7之类的某些元素，然后执行弹出操作四次，则输出将分别为7、9、7、6。

为了解决这个问题，我们将遵循以下步骤-

  • 定义一个映射

  • 定义一个映射站

  • 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

以上是 C ++中的最大频率堆栈 的全部内容， 来源链接： utcz.com/z/335183.html

回到顶部