查找多數元件

Question

我無法解決這一常見的問題有輕微的扭曲：

給定n的每個盒具有單個隱藏數內，並且決定如果兩個框包含一個測試程序相同或不同的數字，確定是否有一個數字出現在大多數框中，即O（n log n）時間內是否有多於n/2個具有相同隱藏數字的框。

我知道摩爾的投票算法，但是這個問題似乎稍有不同。

Answer 1

您可以原樣使用Moore的投票算法（在O（n）時間和O（1）空間中完成）。

從Moore's own website摘自：

我們會從起始位置掃下來的序列。

在我們掃描時，我們保持一對由當前候選人和一個計數器組成。首先，目前的候選人是未知的，計數器爲0

當我們在一個元素e向前移動指針：

• 如果計數器爲0，我們設置當前候選e和我們設置計數器爲1.
• 如果計數器不是0，我們根據e是否爲當前候選項來增加或減少計數器。

當我們完成後，當前候選人是多數元素，如果有多數。

Later in that example：

在一些你知道的，或承擔的情況下，有一大部分元素。

但是，如果您必須確認所選元素確實是大多數元素，則必須再採用一次線性傳遞才能完成此操作。

由於該算法僅涉及檢查當前候選人是否匹配e，只需進行相等性檢查就足夠了。

要檢查最終候選人是否是多數元素，只需再次通過，將每個元素與候選人進行比較並計算匹配數。如果匹配數量大於n/2，那麼確實發現了大多數元素。