如何在允许添加和删除的数字流中找到最频繁的元素

Question

我是新来的论坛，但我已阅读指南并检查重复项（这是最接近的我发现:(How to find the most frequent word in a word stream?），但此搜索对于发生超过51％的时间的数字，请指向我一个重复，如果它已经存在

所以我的问题给了一串数字，找到最频繁发生的数字 例如：2 ，3,4,2,5：Ans = 2. 这很简单，但是如果我可以删除并添加新的数字，会发生什么。 示例：2,3,5,3,4,2,2：Max = 2 删除（2）：最大值= 2;删除（2）：最大值= 3 ...

我想到了一个最大堆随着一个哈希表，包含指向堆中的每个节点的指针，以便更新为O（log n）并找到最大值为O（1）。有更好的解决方案吗？

Answer 1

如果您主要关注快速更新，则可以使用将键（整数）与值（每个整数的当前外观计数）相关联的任何数据结构。 “添加”和“删除”整数将简单地通过递增和递减外观计数来处理。

对于基于二叉树的容器，操作将是O（logN），而对于散列表则为O（1）。在每种情况下，“找到最大值”将是O（N）。

如果您对快速“找到最大值”感兴趣，那么您提出的解决方案就会达到最佳效果。