最大频率栈-问答-阿里云开发者社区-阿里云

开发者社区> 问答> 正文

最大频率栈

Runt 2020-04-14 18:25:31 1233

题目:最大频率栈。

实现 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]。

出题人:阿里巴巴出题专家:屹平/阿里云视频云边缘计算高级技术专家

边缘计算
分享到
取消 提交回答
全部回答(1)
  • Runt
    2020-04-14 18:26:03

    参考答案: 令 freq 作为 x 的出现次数的映射 Map。

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

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

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

    算法:

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

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

    参考代码*:

        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;
        }
    }
    
    0 0
IoT
使用钉钉扫一扫加入圈子
+ 订阅

物联网软硬件开发者一站式基地

推荐文章
相似问题