劍指Offer（二十八）：數組中出現次數超過一半的數字

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        if(numbers.empty()){
            return 0;
        }
        // 周遊每個元素，并記錄次數；若與前一個元素相同，則次數加1，否則次數減1
        int result = numbers[0];
        int times = 1;
        for(int i = 1; i < numbers.size(); ++i){
            if(times == 0){
                // 更新result的值為目前元素，并置次數為1
                result = numbers[i];
                times = 1;
            }
            else if(numbers[i] == result){
                times++;
            }
            else{
                times--;
            }
        }
        // 判斷result是否符合條件，即出現次數大于數組長度的一半
        times = 0;
        for(int i = 0; i < numbers.size(); ++i)
        {
            if(numbers[i] == result){
                times++;
            }
        }
        return (times > (numbers.size() >> 1)) ? result : 0;
    }
};
           

class Solution {//複雜度大一些
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        int size=numbers.size();
        if(size==0){
            return 0;
        }
        for(int i=0;i<size;i++){
            int k=0;
            for(int j=0;j<size;j++){
                if(numbers[i]==numbers[j]){
                    k++;
                }
            }
            if(k>size/2){
                return numbers[i];
            }
        }
        return 0;
    
    }
};