ムーア投票アルゴリズム

Boyer-Mooore majority vote algorithm(ムーア投票アルゴリズム)は、線形時間複雑度と定数レベルの空間複雑度のアルゴリズムであり、要素系列の共通数を検索するために使用される.Robert S.BoyerとJ Strother Mooreの二人の名前を使って命名された典型的な流れアルゴリズムです.
このアルゴリズムの最も簡単な形式は、最も多く現れる要素を探します.つまり、入力の半分以上の重複要素を見つけます.しかし、この数が存在しない場合、アルゴリズムは真実の結果を検出できないが、入力要素のうちの1つの要素を出力します.しかし、入力シーケンスをもう一度巡回して、リターン要素の出現回数を計算して、それが本当かどうかを確認します.
アルゴリズムは、その局所変数において、一時変数mとカウンタcとを維持し、カウンタの初期値はゼロである.そして、私たちはシーケンスの各要素を巡回します.c==0の場合、m=x;c=1;(xは、私たちが遍歴した要素を示す).m==xなら、c++、そうでなければc--.最後にmを返したら良い.
これは疑似コードで以下のステップとして表現できます.

は、一つの要素mと一つの計算機c=0

を初期化する.

は、入力シーケンスの各要素xについて

もしi == 0なら、m = x、i = 1

もしm == xなら、c++、そうでなければc--

はm

を返します.
例を挙げます

[ 1 1 1 2 2 3 1] m = 0, c = 0
[*1 1 1 2 2 3 1] m = 1, c = 1
[1 *1 1 2 2 3 1] m = 1, c = 2
[1 1 *1 2 2 3 1] m = 1, c = 3
[1 1 1 *2 2 3 1] m = 1, c = 2
[1 1 1 2 *2 3 1] m = 1, c = 1
[1 1 1 2 2 *3 1] m = 1, c = 0
[1 1 1 2 2 3 *1] m = 1, c = 1

実際にはこのプロセスはスタックと似ている.私たちが最初の要素1に出会うと、彼をスタックに押し込みます.

stack: 1

続いて一連の1にぶつかって、連続的にスタックをおさえて、なりました.

stack: 1 1 1

2に出会うと、2とスタックトップ要素1とは異なるので、スタックトップ要素をイジェクトする必要があります.後の要素は同じように動作し、最後にスタックトップ要素に戻ります.このように、スタック動作は2とmの2つの要素によってのみシミュレーションされている.

class Solution 
{
public:
    /*
     * @param nums: a list of integers
     * @return: find a  majority number
     */
    int majorityNumber(vector<int> &nums) 
    {
        int c = 0, m = nums[0];
        for (auto num : nums)
        {
            if (c == 0)
            {
                m = num; ++c;
            }
            else if (m == num) ++c;
            else --c;
        }
        // check if there is a majority
        int counter = 0;
        for (auto num : nums) 
        {
            if (num == m) counter++;
        }
        if (counter < (nums.size() + 1) / 2) return -1;        
        return m;
    }
};

reference:
https://en.wikipedia.org/wiki/Boyer–Moore_majorityvote_algorithm
https://helloacm.com/data-structures-algorithms-series-majority-number-boyer-moore-majority-vote-algorithm/