【剑指 offer】数组中出现次数超过一半的数字。

1、题目描述

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

假设数组非空，并且一定存在满足条件的数字。

思考题：

假设要求只能使用 O(n) 的时间和额外 O(1) 的空间，该怎么做呢？

样例

输入：[1,2,1,1,3]
输出：1

2、问题描述：

3、问题关键：

• 出现超过一半，那么它的数量一定其他所以数的之和还要多。
• **用一个count记录当前数的和其他数之差，如果遇到当前数就加1，否则减1，如果为0那么，改变当前设定值。

4、C++代码：

class Solution {
public:
    int moreThanHalfNum_Solution(vector<int>& nums) {
        int count = 1, val = nums[0];//假设第一个就是最多的。记录为1.
        for (int i = 1; i < nums.size(); i ++) {
            if (nums[i] == val) count ++;//遇到相同值就加1，否则减1.
            else count --;
            if (count == 0) {//为0，那么就假设最多的是当前值。
                val = nums[i];
                count = 1;
            }
        }
        return val;
    }
};