查找是否有在出現的陣列的數目超過N/8倍

Question

的問題是：

描述了一種算法，在O（n）的發現的時間，如果存在n個數字，一個陣列出現超過n/8次的數字。

現在我有這就是答案：

我們會做的選擇在地方的數字：N/9,2 * N/9,3 * N/9，...，8 * N/9，並且檢查這8位候選人中是否有一位出現至少n/8次。

但我不明白爲什麼會這個算法的工作。

例如，考慮以下數組： [3,3,1,3,2,3,4,3,5,3,6,3,7,3,8,3,9,3] 。

因此，這裏n = 18，如果這個算法的候選人將是1,2,4,5,6,7,8,9，當我們檢查這些數字是否至少出現n/8次答案將是否定的，但實際上3答案是肯定的。

所以我不明白這是爲什麼算法正確...

Answer 1

這裏的關鍵結論是選擇，資本尤其是當有特殊的意義：它引用找到的第k在最大的入境問題一個未排序的數組。也許有點令人驚訝的先驗，這可以在線性時間內完成，例如使用5中位數樞軸策略與QuickSelect算法相結合。所以如果你用大寫字母S選擇n/9，2n/9，...條目（成本：9 *線性 - 這是線性的），你一定會找到任何出現n/8次的條目。然後再次遍歷數組以計算每個候選項的出現次數，然後重新開始。