問題：給定一個大小為 n 的數(shù)組 nums ，返回其中的多數(shù)元素。多數(shù)元素是指在數(shù)組中出現(xiàn)次數(shù)大于 ? n/2 ? 的元素。

你可以假設(shè)數(shù)組是非空的，并且給定的數(shù)組總是存在多數(shù)元素。

解決的問題是如何在任意多的候選人（選票無序），選出獲得票數(shù)最多的那個。常見的算法是掃描一遍選票，對每個候選人進(jìn)行統(tǒng)計的選票進(jìn)行統(tǒng)計。當(dāng)候選人的數(shù)目固定時，這個常見算法的時間復(fù)雜度為：O(n)，當(dāng)候選人的數(shù)目不定時，統(tǒng)計選票可能會執(zhí)行較長時間，可能需運(yùn)行O(n2)的時間。當(dāng)選票有序時，可以很容易編出O(n)的程序，首先找到中位數(shù)，然后檢查中位數(shù)的個數(shù)是否超過選票的一半。這篇論文針對無序且侯選人不定的情形，提出了摩爾投票算法。算法的比較次數(shù)最多是選票（記為n）的兩倍，可以在O(n)時間內(nèi)選出獲票最多的，空間開銷為O(1)。

class?Solution?{

public:

????int?majorityElement(vector<int>&?nums)?{

???int?candidate=0,vote=0;? //candidate 為候選人 vote代表票數(shù)

???for(int?i:nums){

???????if(vote==0){

???????????candidate=i;

???????????vote=1;

???????}?else?{

???????????if(i == candidate) {

???????????????++vote;

???????????}?else?if(i!=candidate){

???????????????--vote;

???????????}

???????}

???}

???return?candidate;

????}

};