在一個數組中發生最大次數的元素

Question

我希望在線性時間內發現大數組中發生最大次數的元素。我正在通過摩爾表決算法頁面。 http://www.cs.utexas.edu/~moore/best-ideas/mjrty/example.html。我認爲moore建議的算法會得到不正確的結果，說如果數組是AAACCBCCCCBDAEFF。它將使F作爲元素出現在數組中。 PLZ點我錯了，PLZ建議一些線性時間算法，而不使用哈希映射。

Answer 1

假設您有abcdefghijklmnopqrstuvwxyzf。

要確定f是多數元素，你必須將它保存在內存中，但是直到你到達第二個f，你沒有任何特殊的理由這樣做。所以這意味着如果你把第一個f保存在內存中，你還保留了其他的字母（26個），基本上它就是使用散列。

我不認爲有可能做你想做的事。