LeetCode 簡(jiǎn)單題目茧泪，記錄一下
已知一組數(shù)中有一個(gè)數(shù)占超過半數(shù)以上蜓氨，求出這個(gè)數(shù)是什么？
該算法的步驟是：首先選定第一個(gè)數(shù)作為“疑似眾數(shù)”队伟，設(shè)定計(jì)數(shù)器為1穴吹。然后往后遍歷，當(dāng)碰到相同的數(shù)嗜侮，計(jì)數(shù)器加1港令，否則減去1。當(dāng)計(jì)數(shù)器等于 0 時(shí)锈颗，重新選擇下一個(gè)數(shù)為疑似眾數(shù)顷霹，直到遍歷完全部數(shù)。最終的疑似眾數(shù)便是所需答案击吱。
解釋如下：分兩種情況考慮淋淀，第一，選中了眾數(shù)本身覆醇，則由于眾數(shù)的數(shù)量比其余的數(shù)字加起來都要多朵纷，所以即時(shí)中途被停止了，也只是減去等量的眾數(shù)和其他數(shù)永脓，對(duì)最終結(jié)果不影響柴罐。第二，選中了其他的數(shù)字憨奸，此時(shí)減去等量的 其他數(shù)B 和（眾數(shù)加上除了B以外的其他數(shù)）革屠，由于其他數(shù)B占比較少，所以一定會(huì)在中途計(jì)數(shù)器等于0排宰。此時(shí)刪除了更多的其他數(shù)：其他數(shù)B = 除了B以外的其他數(shù) +?眾數(shù) >>?其他數(shù)B +?除了B以外的其他數(shù) >?眾數(shù) , 故剩下的眾數(shù)數(shù)量更加多似芝，因此對(duì)結(jié)果沒有影響。
下面給出 C++ 代碼：
class?Solution?{
public:
????int?majorityElement(vector<int>&?nums)?{
????????int?major?=?nums[0];
????????int?count?=?1;
????????for(int?i?=?1;i?<?nums.size();?i++){
????????????if(count?!=?0){
????????????????if(nums[i]?!=?major)?count--;
????????????????else?count++;
????????????}
????????????else{
????????????????major?=?nums[i];
????????????????count++;
????????????}
????????}
????????return?major;
????}
};
