题解 | #数组中出现次数超过一半的数字#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numbers int整型vector 
     * @return int整型
     */
    int MoreThanHalfNum_Solution(vector<int>& numbers) {
        // write code here
        //使用摩尔投票
        if(numbers.size() == 0)return -1;
        pair<int,int> tmp;
        tmp.first = numbers[0];
        tmp.second = 0;
        for(int& val: numbers){
            if(val == tmp.first){
                tmp.second += 1;
            }else{
                tmp.second -= 1;
                if(tmp.second == 0){
                    tmp.first = val;
                    tmp.second = 1;
                }
            }
        }
        return tmp.first;
    }
};

题解：该题使用摩尔投票。从头开始，如果遇到相同的数就加一表示出现次数加1，如果不同则减一，如果此时当前数出现为0，那么就要换候选人，其出现次数置为1。遍历完整个数组，最后的候选人即为出现次数超过一半的。时间复杂度是O(n),空间复杂度是O(1)。