如何在允许添加和删除的数字流中查找最频繁的元素 [英] How to find the most frequent element in a stream of numbers with additions and deletions allowed

问题描述

我是这个论坛的新手，但我已阅读指南并检查是否有重复（这是我找到的最接近的内容：（如何在单词流中找到最频繁的单词？），但这会搜索出现率超过51％的数字。

I am new to the forum but I have read the guidelines and checked for duplicates( This is the closest I found :(How to find the most frequent word in a word stream?) but this searches for numbers that occur more than 51 % of the time. Please point me to a duplicate if it already exists.

因此，给我的问题提供了一连串数字，请找出出现频率最高的数字。例如，
：2,3,4,2,5：Ans =2。
这很简单，但是如果我可以删除并添加新数字，会发生什么情况。
例如：2,3,5,3,4， 2,2：Max = 2
Delete（2）：Max = 2; Delete（2）：Max = 3 ...

So my questions is given a stream of numbers, find the number that occurs most frequently. For example : 2,3,4,2,5 : Ans = 2. This is easy but what happens if I can delete and add new numbers. Example : 2,3,5,3,4,2,2 : Max = 2 Delete(2) : Max = 2 ; Delete(2) : Max = 3 ...

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

I have thought of a Max heap Along with a Hash Table that contains pointers to each node in the heap so that updation is O(log n) and finding the max is O(1). Is there a better solution ?

推荐答案

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

If you are interested mostly in fast updates, you can use any data structure that associates keys (the integers) with values (each integer's current appearance count). "Adding" and "removing" integers will be simply handled by incrementing and decrementing the appearance count.

对于基于二叉树的容器，操作将为O（logN），而对于哈希表，它将是O（1）。在每种情况下，查找最大值都是O（N）。

For containers based on binary trees the operations would be O(logN) while for a hashtable it would be O(1). In each case "find the maximum" would be O(N).

如果您对快速查找最大值感兴趣，那么建议的解决方案就和它会得到。

If you are interested mostly in fast "find the maximum" then your proposed solution is as good as it gets.

这篇关于如何在允许添加和删除的数字流中查找最频繁的元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！