169.衆数を求める(C++)

169.衆数を求める

問題説明

アルゴリズム思想

コード

問題の説明
nの大きさの配列を与え,その中の衆数を見つけた.衆数とは,配列に現れる回数がn/2⌋より大きい要素を指す.
配列は空ではなく、与えられた配列は常に衆数が存在すると仮定することができます.
例1:
入力:[3,2,3]出力:3例2:
入力:[2,2,1,1,2,2]出力:2
アルゴリズム思想
最も簡単な直接的な方法は、まず並べ替えて、それから容器の真ん中の数に戻ればいいです.
実は本題にはもう一つの考え方があります.モル投票アルゴリズムの応用です.Moore majority vote algorithm(ムーア投票アルゴリズム)Boyer-Moore majority vote algorithm(ムーア投票アルゴリズム)概要Boyer-Moore majority vote algorithm(ムーア投票アルゴリズム)は、線形時間O(n)と空間的複雑度の場合に、1つの要素配列の中で最も多く含まれる要素を検索するものである.これはRobert S.BoyerとJ Strother Mooreによって命名され、1981年に発明された典型的なストリームアルゴリズム(streaming algorithm)である.
最も簡単な形式は、最も多くの要素を検索することです.つまり、入力の半分以上(n/2)が繰り返される要素です.シーケンスに最も多くの要素がない場合、アルゴリズムは正しい結果を検出できず、要素の1つを出力します.
要素の繰返し回数が比較的小さい場合、ストリームアルゴリズムでは、線形空間よりも小さい場合に最も周波数の高い要素を検索することはできません.
アルゴリズム記述アルゴリズムは、局所変数においてシーケンス要素(m)とカウンタ(i)を定義し、初期化の場合、カウンタは0である.アルゴリズムはシーケンス中の要素を順次スキャンし、要素xを処理するとき、カウンタが0の場合、xをmに割り当て、カウンタ(i)を1に設定し、カウンタが0でない場合、シーケンス要素mとxを比較し、等しい場合、カウンタに1を加え、等しくない場合、カウンタは1を減算する.処理後、最後に格納されるシーケンス要素(m)は、このシーケンスで最も多くの要素である.
記憶されている要素mが最も多くの要素であるか否かが不明であれば、2回目のスキャンを行って最も多くの要素であるか否かを判断することもできる.
コード#コード#
ツールバーの

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        return  nums[nums.size()/2];
    }
};

モル投票法

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int count=1;
        int i;
		int maj=nums[0];
		for (i=1; i<nums.size();i++) 
        {
			if (maj==nums[i])
				count++;
			else 
            {
				count--;
				if(count==0)
                {
					maj=nums[i+1];
				}
			}
		}
		return maj;
    }
};