由于我們要找的數(shù)字出現(xiàn)的次數(shù)比其他所有數(shù)字出現(xiàn)的次數(shù)之和還要多，那么要找的數(shù)字肯定是最后一次把次數(shù)設(shè)為1時(shí)對(duì)應(yīng)的數(shù)字沪么。我們維護(hù)兩個(gè)變量，num和count,其中num為保存的數(shù)字，count為保存的數(shù)字的統(tǒng)計(jì)。
由于這是一個(gè)必要非充分條件请祖，因此需要驗(yàn)證一下订歪。
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers) {
int len = numbers.size();
if(len==0) return 0;
int num = numbers[0],count = 1;
for(int i = 1;i<len;++i){
if(numbers[i]==num) ++count;
else --count;
if(count==0){ //放心脖祈，這里的count是不可能＜0的
num = numbers[i];
count = 1;
}
}
//驗(yàn)證
count = 0;
for(int i = 0;i<len;++i){
if(numbers[i]==num)
count++;
}
return count>(len/2)?num:0;
}
};
