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

public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        // 408题
        // 方法一：遍历 存hash，再遍历，返回hash的值大于长度一半的值（空间复杂度超了）
        // 假设第一个就是，从前向后遍历，统计次数，出现不一样的就次数-1，如果说减完小于0了，则替换当前比较值为新的结果
        // 直到遍历结束，结果肯定是count>=0的一个数
        // 原理：
        // 因为要找的是出现次数超过一半的数字，所以说，一个这个数字和其他数字两两删除，剩下的肯定是这个超过一半的数字
        // 所以从前向后遍历，出现超过一般的数字肯定会是留到最后的数字。
        
        int count=0;
        int ans=numbers[0];
        // 向后遍历
        for(int i=0;i<numbers.size();i++)
        {
            // 是预测的就+1
            if(numbers[i]==ans)
                count++;
            else{
                // 不是预测的就-1，如果结果小于0了，则重新预测
                count--;
                if(count<0){
                    ans=numbers[i];
                    count=1;
                }
            }
        }
        return ans;
    }
};