0

我是论坛的新手，但我已经阅读了指南并检查了重复项（这是我找到的最接近的：（如何在词流中找到最常见的词？）但这会搜索出现超过 51% 的数字时间。如果它已经存在，请给我指出一个副本。

所以我的问题是给定一个数字流，找到最常出现的数字。例如：2,3,4,2,5：Ans = 2。这很简单，但如果我可以删除和添加新数字会发生什么。示例：2,3,5,3,4,2,2：Max = 2 Delete(2)：Max = 2；删除（2）：最大 = 3 ...

我想到了一个最大堆以及一个包含指向堆中每个节点的指针的哈希表，因此更新为 O(log n)，找到最大值为 O(1)。有更好的解决方案吗？

4

1 回答 1

1

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

对于基于二叉树的容器，操作为 O(logN)，而对于哈希表，操作为 O(1)。在每种情况下，“找到最大值”都是 O(N)。

如果您主要对快速“找到最大值”感兴趣，那么您提出的解决方案就是最好的。

于 2013-02-25T12:31:49.983 回答