跟着姚桑学算法-数组中出现次数超过一半的数字

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

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

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

思考题：

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

数据范围
数组长度 [1,1000]。

样例

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

输出：1

【题解】-- 枚举

1. 考虑需要遍历整个数组；
2. 考虑可以设定一个计数器，记录重复的那个数的个数，所以有了cont；另外需要输出重复的那个数，所以有了val；
3. 数组中的数，我们可以假设为x。

开始遍历第一个x，此时计数器+1，cont=1;val=x。
如果下一个数还是x，那么val还是等于x，cont=2;
假设第三个数为y，那么cont此时等于2-1=1，val还是x,
如果第四个数还是z，那么cont此时等于1-1=0；此时符合开头if(!cont) 这个条件，那么val变成了z的值；

如此通过计数来确定val的值，最后留下了的即重复的那个数，因为他出现的次数过一半。

复杂度分析：

暴力枚举的时间复杂度为O（n^2）。

C++代码实现：

class Solution {
public:
    int moreThanHalfNum_Solution(vector<int>& nums) {
        int cont =0, val= 0;
        //循环遍历数组nums
        for(auto x:nums)
        {
            if(!cont) val =x , cont =1;//如果cont 计数器为零 val等于数组中的x,计数器为1；
            else//计数器cont不为零的时候
            {
                if(x==val) cont++;//如果说x的值等于val当前那么就++；
                //x不等于val当前值，计数器减，但是val还是不变的，除非cont变成了0了，再遍历下一个的时候val变成了下一个x,计数器为1
                else cont--;
            }

        }
        return val;
    }
};