如何在允許添加和刪除的數字流中找到最頻繁的元素

我是新來的論壇，但我已閱讀指南並檢查重複項（這是最接近的我發現:(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）。有更好的解決方案嗎？

2013-02-25 Jon Smith

請嘗試以下http://stackoverflow.com/questions/3740371/finding-the-max-repeated-element-in-array – 2013-02-25 12:35:56

如果您主要關注快速更新，則可以使用將鍵（整數）與值（每個整數的當前外觀計數）相關聯的任何數據結構。「添加」和「刪除」整數將簡單地通過遞增和遞減外觀計數來處理。

對於基於二叉樹的容器，操作將是O（logN），而對於散列表則爲O（1）。在每種情況下，「找到最大值」將是O（N）。

如果您對快速「找到最大值」感興趣，那麼您提出的解決方案就會達到最佳效果。

2013-02-25 12:31:49 Jon

我主要是在優化「找到最大」感興趣，所以只是一個哈希表格將不起作用，因爲查找最大值將是O（N）。感謝您的輸入！ – 2013-02-25 12:42:50

回答