我需要改进这个问题的有效解决方案：
系统从网络中的用户获取消息。每次用户发布消息时，我们都会增加该用户的总计数器（totCounter）和用户的消息计数器（userMessagesCounter）。为此，我们有一个包含users（键）和userMessagesCounter（值）的哈希映射。因此，为了获得在网络中发送超过10%消息的用户，我们所做的就是迭代哈希表，检查每个用户是否（userMessagesCounter/totCounter）>0.1，如果是，我们将用户密钥添加到ArrayList中。最后我们返回这个列表。这需要O（n），因为我们对所有用户进行迭代。
我需要改进这个系统，使它以我所能达到的最快速度运行。我想到的是这样一个事实：负载超过10%的用户不可能超过10个（因为我们的负载超过100%）。因此，我可以制作一个大小为10的数组，并在消息到达时更新它。问题是，当新消息到达时，此数组信息可能不再有效，我需要重新检查每个到达消息的所有数组元素。
有人知道如何使用我提出的想法来解决O（10）中的这个问题吗？
非常感谢。
您正在寻找频繁挖掘算法，该算法查找在集合中重复theta（在您的情况下为theta=0.1）次的项。
Karp Papadimitriou Shanker提出了一种在线性时间中使用1/theta空间处理它的方法：一种寻找频繁项的简单算法流和袋中的元素
1. PF = ∅
2. foreach element e∈S {
3. if PF.hasKey(e) { // increase counter
4. PF.value(e)++ // of existing elements
5. }
6. Else {
7. PF.insert(e,1) // insert new element
8. If |PF|== 1/θ { // but if PF is full
9. Foreach key ∈ PF {
10. PF.value(k)-- // decrease all counters
11. if PF.value(k) == 0 { // and remove
12. PF.remove(k) // elements at 0
13. } } } } }
14. Output PF
Tehcnion大数据课程讲义中的伪代码
在这里，您的"；流"；是发送的消息，当您查找具有频繁消息的用户时，请检查PF中的当前候选者，这是常数theta=0.1的O(1)。
该算法产生了CCD_ 7（在您的情况下为10）个候选；"频繁"；，但它有假阳性——这意味着它可能指向"；可能频繁"；，虽然不是，但这对你来说应该不难，因为你可以简单地验证它，
我想我在这里看到了一个接近O（1）的解决方案：
维护一个包含用户列表及其邮件计数的词典。
您有一个10%用户的列表。这些是指向词典记录的链接，而不是本地副本。
当你收到一条消息时，你会查找该用户并增加他们的消息计数。这是O（1），因为它是一本字典。如果计数小于10%，则退出。
如果此用户已在10%列表中，请退出。如果列表按用户排序，则为O（4），否则为O（10）。
将此用户添加到10%列表中。
清除不再是10%用户的所有用户的列表。最坏的情况是O（10）。
请求列表时：
清除不再是10%用户的所有用户的列表。同样，O（10）在最坏的情况下——这与上面的例程相同。
返回列表的副本。