最大频率栈

妖狐艹你老母 2023-06-09 11:28 77阅读 0赞

**题目**：最大频率栈。

实现 FreqStack，模拟类似栈的数据结构的操作的一个类。FreqStack 有两个函数： push(int x)，将整数 x 推入栈中。pop()，它移除并返回栈中出现最频繁的元素。如果最频繁的元素不只一个，则移除并返回最接近栈顶的元素。 ◼ 示例： push \[5,7,5,7,4,5\] pop() -> 返回 5，因为 5 是出现频率最高的。 栈变成 \[5,7,5,7,4\]。 pop() -> 返回 7，因为 5 和 7 都是频率最高的，但 7 最接近栈 顶。 栈变成 \[5,7,5,4\]。 pop() -> 返回 5 。 栈变成 \[5,7,4\]。 pop() -> 返回 4 。 栈变成 \[5,7\]。

**参考答案**：

令 freq 作为 x 的出现次数的映射 Map。

此外 maxfreq，即栈中任意元素的当前最大频率，因为我们必须弹出频率最高的元素。

当前主要的问题就变成了：在具有相同的（最大）频率的元素中，怎么判断那个元素是最新的？我们可以使用栈来查询这一信息：靠近栈顶的元素总是相对更新一些。

为此，我们令 group 作为从频率到具有该频率的元素的映射。到目前，我们已经实现了 FreqStack 的所有必要的组件。

算法：

实际上，作为实现层面上的一点细节，如果 x 的频率为 f，那么我们将获取在所有 group\[i\] (i <= f) 中的 x,而不仅仅是栈顶的那个。这是因为每个 group\[i\] 都会存储与第 i 个 x 副本相关的信息。

最后，我们仅仅需要如上所述维持 freq，group，以及 maxfreq。

示例：

输入：  
\["FreqStack","push","push","push","push","push","push","pop","pop","pop","pop"\],  
\[\[\],\[5\],\[7\],\[5\],\[7\],\[4\],\[5\],\[\],\[\],\[\],\[\]\]  
输出：\[null,null,null,null,null,null,null,5,7,5,4\]  
解释：  
执行六次 .push 操作后，栈自底向上为 \[5,7,5,7,4,5\]。然后：

pop() -> 返回 5，因为 5 是出现频率最高的。  
栈变成 \[5,7,5,7,4\]。

pop() -> 返回 7，因为 5 和 7 都是频率最高的，但 7 最接近栈顶。  
栈变成 \[5,7,5,4\]。

pop() -> 返回 5 。  
栈变成 \[5,7,4\]。

pop() -> 返回 4 。  
栈变成 \[5,7\]。  
提示：

对 FreqStack.push(int x) 的调用中 0 <= x <= 10^9。  
如果栈的元素数目为零，则保证不会调用  FreqStack.pop()。  
单个测试样例中，对 FreqStack.push 的总调用次数不会超过 10000。  
单个测试样例中，对 FreqStack.pop 的总调用次数不会超过 10000。  
所有测试样例中，对 FreqStack.push 和 FreqStack.pop 的总调用次数不会超过 150000。

**JAVA代码**\*：

class FreqStack {
        Map<Integer, Integer> freq;
        Map<Integer, Stack<Integer>> group;
        int maxfreq;
    
        public FreqStack() {
            freq = new HashMap();
            group = new HashMap();
            maxfreq = 0;
        }
        
        public void push(int x) {
            int f = freq.getOrDefault(x, 0) + 1;
            freq.put(x, f);
            if (f > maxfreq) maxfreq = f;
            group.computeIfAbsent(f, z-> new Stack()).push(x);
        }
        
        public int pop() {
            int x = group.get(maxfreq).pop();
            freq.put(x, freq.get(x) - 1);
            if (group.get(maxfreq).size() == 0)
            maxfreq--;
            return x;
        }
    }

# C++代码： #

# 思路1： #

本人思路：需要用到：一个优先队列p，一个map ma，两个栈q,qu。结构体MY（第一个元素是原数值，第二个元素是该数值出现的频数）

优先队列每一个元素都是一个MY，根据频数由大到小排序，map键是原数值，值是该数值出现的实时频数，队列用来存放数值

对于每个push操作x：首先map记录加一，然后把map的值和对应的键插入优先队列。如果优先队列之前就有这个键的MY了也没有关系，因为ma\[x\]记载的是x实时的频数，在取数的时候，如果队列中MY.频数！=ma\[x\]的话，这个记录肯定是无效的。

对于每个pop：首先找到优先队列中第一个有效元素，也就是x是MY的第一个元素的情况下，MY第二个元素和ma\[x\]相同，

找到这个有效MY之后，记录这个MY出现的频数ans，这肯定是当前最大的频数，然后遍历栈q，直到有一个元素x的当前次数ma\[x\]等于ans，在遍历的过程中把元素放到qu中，待到之后再把qu的元素放回去，因为每次只需要删一个，其他元素需要还原。

代码：

class FreqStack {
    public:
    struct MY{
        int yu,ra;
        MY(){}
        MY(int x,int y):yu(x),ra(y){}
        bool operator<(const MY &m)const{
            return ra<m.ra;
        }
    };
     
    priority_queue<MY>p;
    map<int,int>ma;
    stack<int>q;
     FreqStack() {
        while(!p.empty()){
            p.pop();
        }
        ma.clear();
        while(!q.empty())q.pop();
    }
     
    void push(int x) {
        int nu = ma[x] + 1;
        ma[x] = nu;
        p.push(MY(x,nu));
        q.push(x);
    }
     
    int pop() {
        int ans = 0,res=0;
        while(!p.empty()){
            MY m = p.top();
            if(ma[m.yu]==m.ra){
                ans = m.ra;
                break;
            }
            p.pop();
        }
        stack<int>qu;
        while(!q.empty()){
            int num = q.top();q.pop();
            if(ma[num]==ans){
                ma[num] = ma[num] - 1;
                res = num;
                break;
            }
            else qu.push(num);
        }
        while(!qu.empty()){
            int num = qu.top();qu.pop();
            q.push(num);
        }
        return res;
    }
     
    };

#    **思路2：** #

还有一种简单的思路：这个题目有两个条件，一个要找出现频率最高的数字，如果只有这一个条件我们可以很简单的用一个优先队列对出现频率排序即可，但是还有一个条件就是在频率相同的时候，需要找栈里面比较新的元素，这个条件可以稍微转变一下，如果我们给每一个入栈的元素一个序号t，后入栈的元素编号肯定大于前面入栈的元素的编号，那么我们不就可以根据这个编号来判断入栈的时间了吗？这样就可以用一个优先队列解决了。所以这一题关键就在于把栈的顺序编号化

代码

struct MY{
        int yu,ra,step;
        MY(){}
        MY(int x,int y,int z):yu(x),ra(y),step(z){}
        bool operator<(const MY &m)const{
            if(ra==m.ra)return step<m.step;
            else return ra<m.ra;
        }
    };
     
    map<int,int>ma;
    priority_queue<MY>p;
    int t = 0;
    FreqStack() {
        while(!p.empty())p.pop();
        ma.clear();
        t = 0;
    }
     
    void push(int x) {
        ma[x] = ma[x] + 1;
        p.push(MY(x,ma[x],t++))
    }
     
    int pop() {
        MY my = p.top();
        int x = my.yu;
        ma[x] = ma[x] - 1;
        p.pop();
        return x;
    }

# 思路3：利用vector和map解决 #

class FreqStack {
    	unordered_map<int64_t, int64_t> freq;
    	unordered_map<int64_t, vector<int64_t>> group;
    	int64_t max_freq;
    public:
    	FreqStack() { max_freq = 0; }
    
    	void push(int64_t x) {
    		max_freq = max(max_freq, ++freq[x]);
    		group[freq[x]].push_back(x);
    	}
    
    	int64_t pop() {
    		int64_t x = group[max_freq].back();
    		group[max_freq].pop_back();
    		if (group[freq[x]--].empty()) --max_freq;
    		return x;
    	}
    };
    
    
    
    //调用
    FreqStack objStack;
    	objStack.push(5);
    	objStack.push(7);
    	objStack.push(8);
    	objStack.push(9);
    	objStack.push(5);
    	objStack.push(7);
    	objStack.push(4);
    	objStack.push(5);
    	int64_t freq = objStack.pop();
    	freq = objStack.pop();
    	freq = objStack.pop();

# 参考链接： #

[https://blog.csdn.net/lwgkzl/article/details/82180809][https_blog.csdn.net_lwgkzl_article_details_82180809]

[https://github.com/debitCrossBlockchain/interview\_\_reference/blob/master/01.%E9%98%BF%E9%87%8C%E7%AF%87/1.3.1%20%E6%9C%80%E5%A4%A7%E9%A2%91%E7%8E%87%E6%A0%88.md][https_github.com_debitCrossBlockchain_interview_reference_blob_master_01._E9_98_BF_E9_87_8C_E7_AF_87_1.3.1_20_E6_9C_80_E5_A4_A7_E9_A2_91_E7_8E_87_E6_A0_88.md]

[https_blog.csdn.net_lwgkzl_article_details_82180809]: https://blog.csdn.net/lwgkzl/article/details/82180809
[https_github.com_debitCrossBlockchain_interview_reference_blob_master_01._E9_98_BF_E9_87_8C_E7_AF_87_1.3.1_20_E6_9C_80_E5_A4_A7_E9_A2_91_E7_8E_87_E6_A0_88.md]: https://github.com/debitCrossBlockchain/interview__reference/blob/master/01.%E9%98%BF%E9%87%8C%E7%AF%87/1.3.1%20%E6%9C%80%E5%A4%A7%E9%A2%91%E7%8E%87%E6%A0%88.md