//摩尔投票法
class Solution {
public:
    int moreThanHalfNum_Solution(vector<int>& nums) {
        int cnt=0;//计数
        int val;//主元
        for(auto x:nums)//用x访问nums的每一个元素项
        {
            if(cnt==0) 
            {
                val=x;
                cnt++;
            }
            else if(x==val) cnt++;
            else cnt--;
        }

        cnt=0;
        for(auto x:nums)
        {
            if(x==val) cnt++;
        }
        if(cnt<=nums.size()/2) return -1;
        else return val;
    }
};