题意：
        给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。


方法一：
计数数组
思路：
        用一个计数数组记录每个数出现的次数。
         先遍历一遍原数组，对数出现次数进行统计，并存储在数组中。
        最后遍历一遍计数数组，如果某个数出现的次数大于数组长度的一半，则返回该数。

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        int cnt[10005];//计数数组
        int n=numbers.size();
        for(int i=0;i<n;i++){//计数
            cnt[numbers[i]]++;
        }
        for(int i=0;i<=10000;i++){
            if(cnt[i]>n/2)//如果某个数出现的次数大于数组长度的一半，则返回该数
                return i;
        }
        return 0;
    }
};

时间复杂度：
空间复杂度：

方法二：
思维

思路：
        思想类似一换一。
        因为我们要的答案数值的个数是超过数组大小的一半，因此当答案数值与其他数一对一的消去后（即一换一），还会剩余答案数值。
        
        将每个数因为数值不同，而规定着属于不同的阵营。
        当一个数遇到不等于本身阵营（即数值不等于自身）时，就一对一消去，最后剩的数肯定是我们所要的答案数值。 



class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        int n=numbers.size();
        int x,cnt=0;
        for(int i=0;i<n;i++){
            if(cnt==0){//当cnt==0,x设置为新值，即新建阵营
                x=numbers[i];
                cnt++;
            }else{
                if(x==numbers[i]){//阵营相同，自增
                    cnt++;
                }else{//阵营不同，自减
                    cnt--;
                }
            }
            
        }
        return x;
    }
};

时间复杂度：
空间复杂度：