題目描述
數(shù)組中有一個(gè)數(shù)字出現(xiàn)的次數(shù)超過(guò)數(shù)組長(zhǎng)度的一半，請(qǐng)找出這個(gè)數(shù)字伊诵。例如輸入一個(gè)長(zhǎng)度為9的數(shù)組{1,2,3,2,2,2,5,4,2}又跛。由于數(shù)字2在數(shù)組中出現(xiàn)了5次嗦董，超過(guò)數(shù)組長(zhǎng)度的一半性芬，因此輸出2峡眶。如果不存在則輸出0。
思路
如果有符合條件的數(shù)字植锉，則它出現(xiàn)的次數(shù)比其他所有數(shù)字出現(xiàn)的次數(shù)和還要多辫樱。
在遍歷數(shù)組時(shí)保存兩個(gè)值：一是數(shù)組中一個(gè)數(shù)字，一是次數(shù)俊庇。遍歷下一個(gè)數(shù)字時(shí)狮暑，若它與之前保存的數(shù)字相同，則次數(shù)加1辉饱，否則次數(shù)減1搬男；若次數(shù)為0，則保存下一個(gè)數(shù)字彭沼，并將次數(shù)置為1缔逛。遍歷結(jié)束后，所保存的數(shù)字即為所求溜腐。然后再判斷它是否符合條件即可译株。
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers) {
if(numbers.empty())
return 0;
// 遍歷每個(gè)元素，并記錄次數(shù)挺益；若與前一個(gè)元素相同歉糜，則次數(shù)加1，否則次數(shù)減1
int result=numbers[0];
int times=1;
for(int i=1;i<numbers.size();i++){
if(times==0){
// 更新result的值為當(dāng)前元素望众，并置次數(shù)為1
result=numbers[i];
times=1;
}
else if(numbers[i]==result)
++times;
else
--times;
}
// 判斷result是否符合條件匪补，即出現(xiàn)次數(shù)大于數(shù)組長(zhǎng)度的一半
times=0;
for(int i=0;i<numbers.size();i++){
if(numbers[i]==result)
++times;
}
return (times>numbers.size()/2)?result:0;
}
};
