查找出現超過n/k次的所有元素

Question

給定一個大小爲n和數字爲k的數組，查找出現超過n/k次的所有元素。

我相信這個問題可以通過使用摩爾投票算法的技術來解決，通過創建一個大小爲k的地圖來存儲數量和頻率。

步驟：

首先創建大小爲k的地圖，並插入從陣列的第一k個元素，並更新其相應的頻率。

如果數字存在於地圖中，則增加它們的計數否則減少具有最低計數值的現有數字的計數（我們可以通過保持另一個地圖在恆定時間內找到該計數）如果計數曾經下降到0從地圖中刪除該號碼並添加新號碼。

最後檢查地圖中的數字是否存在頻率大於n/k。

我期待您的反例或評論。

例如：考慮N = 10和K = 2

考慮場景

2,2,2,7,1,3,5,6,8,9

地圖將具有尺寸2.

對於第一元件它將只包含2與計數3. 7，它將插入（因爲圖具有空閒塊），並更新它計數1. 1是在地圖上不找到在這種情況下，最低的候選人數是7現在減少它的計數7的計數是0，因此通過插入1和設置計數1來更新輸入。 此過程將一直進行到陣列末尾，我們在地圖2和9中剩下兩個候選項，它們的計數爲3和1

我們將檢查計數> n/k的元素和返回結果的計數。 （我們不需要循環數組k次，我們可以將計數最初存儲在其他地圖中），所以在最後檢查候選人的計數時，我們將執行O（k）運算。

Answer 1

這不起作用。取數a，在陣列開始時出現int(n/k + 1)次，隨後是一些隨機混合的n-int(n/k+1)號碼不再包含a了。由於n-int(n/k+1)對於k>2大於int(n/k+1)，因此不能保證a的數組條目不會降爲零。

該算法的改進版本不產生假陰性（但可能產生假陽性）在Data Streams: Algorithms and Applications By S. Muthukrishnan的第5.1.2節「頻繁元素/重擊者採樣」中。