数组中出现次数超过一半的数字

题目描述

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

代码

class Solution {
public:
    //有数字出现的次数超过数组长度的一半，说明该数字的个数会大于其它数字个数的和
    //所以维护一个候选数以及候选数的个数,如果候选数的个数为0时（说明前面的数肯定是一半是相同的，两两抵消），当前数变更为候选数，重新计数为1。
    int MoreThanHalfNum_Solution(vector<int> numbers) {
    	int c = 0 , cnt = 0;
        for (auto num : numbers) {
            if (cnt == 0) {
                c = num;
                cnt = 1;
            } else {
                c == num ? ++cnt : --cnt;
            }
        }
        cnt = 0;
        for (auto num : numbers) {
            if (num == c) {
                ++cnt;
            }
        }
        return (cnt << 1) > (numbers.size()) ? c : 0;
    }
};