[169] Majority Element

奇怪我看我的submit 紀錄有送過AC，但是部洛格裡面沒有寫XD

怎麼會這樣呢 ？（thinking 圖）（可能是貼別人的扣跑跑看嗎XD）

也好，又看了一個新的解法！

Majority Element的意思是一個array裡面有一個值它出現的次數大於array長度的一半

直覺算法當然是去算每個值總共出現幾次，

另有一說是先把array排序，因為它的出現次數大於一半，所以排序完回傳中間的值就可以了～它必定是那個出現超過一半的人

最後看到神秘解法！（還有神秘網站）

Boyer-Moore Majority Vote Algorithm

http://www.cs.utexas.edu/~moore/best-ideas/mjrty/

它每次去count現在的element 和現有的相不相同

若相同就加一，若不同就減一，當回到零的時候就更新這個element為新的值

注意更新的時機點！（回到零的時候, 新的element 為下一個值 ！）

int majorityElement(int* nums, int numsSize){

int count =0;

int currNum=nums[0];

for (int i=0;i<numsSize;i++)

{

if (currNum ==nums[i])

count++;

else

count--;

if (count==0 && (i+1)<numsSize)

currNum=nums[i+1];

}

return currNum;

}