Moore's voting algorithm

最近在刷LeetCode的題的時候，發現一個特别巧妙的算法：Moore’s voting algorithm。

這個算法是解決這樣一個問題：從一個數組中找出出現半數以上的元素。

Moore的首頁上有這個算法的介紹：A Linear Time Majority Vote Algorithm和這個算法的一個簡單示例示範：示範連結。

算法的基本思想

每次都找出一對不同的元素，從數組中删掉，直到數組為空或隻有一種元素。 不難證明，如果存在元素e出現頻率超過半數，那麼數組中最後剩下的就隻有e。

當然，最後剩下的元素也可能并沒有出現半數以上。比如說數組是[1, 2, 3]，最後剩下的3顯然隻出現了1次，并不到半數。排除這種false positive情況的方法也很簡單，隻要儲存下原始數組，最後掃描一遍驗證一下就可以了。

算法的實作

在算法執行過程中，我們使用常量空間實時記錄一個候選元素c以及其出現次數f(c)，c即為目前階段出現次數超過半數的元素。

在周遊開始之前，該元素c為空，f(c)=0。

然後在周遊數組A時，如果f(c)為0，表示目前并沒有候選元素，也就是說之前的周遊過程中并沒有找到超過半數的元素。那麼，如果超過半數的元素c存在，那麼c在剩下的子數組中，出現次數也一定超過半數。是以我們可以将原始問題轉化為它的子問題。此時c指派為目前元素, 同時f(c)=1。

如果目前元素A[i] == c, 那麼f(c) += 1。(沒有找到不同元素，隻需要把相同元素累計起來)

如果目前元素A[i] != c，那麼f(c) -= 1。 (相當于删除1個c)，不對A[i]做任何處理(相當于删除A[i])

如果周遊結束之後，f(c)不為0，那麼元素c即為尋找的元素。上述算法的時間複雜度為O(n)，而由于并不需要真的删除數組元素，我們也并不需要額外的空間來儲存原始數組，空間複雜度為O(1)。

C++代碼實作如下：

int majorityElement(vector<int> &num)
{
    int curIdx = , count = ;
    for (int i = ; i < num.size(); ++i)
    {
        num[i] == num[curIdx] ? ++count : --count;
        if (!count)
        {
            curIdx = i;
            count = ;
        }
    }

    return num[curIdx];
}