class Solution {

 public:

     int MoreThanHalfNum_Solution(vector<int> numbers) {

         // 从数组中移除两个不相同的数值，如果有出现的次数超过数组长度的一半的数，那么就是最后剩下来的那个

         int numSize = numbers.size();

         int candidate = ;  // 候选数，可能是出现的次数超过数组长度的一半的数

         int cnt = ;    // 标记当前的候选数没被抵消的次数

         for(int i = ; i < numSize; i++) {

             if(cnt == ) candidate = numbers[i];    // 重选候选数

             if(candidate == numbers[i]) cnt++;  // 次数加1

             else cnt--; // 次数减1

         }

         cnt = ;

         for(int i = ; i < numSize; i++)    // 检验

             if(numbers[i] == candidate)

                 cnt++;

         if(cnt *  <= numSize) return ;

         return candidate;

     }

 };