题目描述：

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

分析：

 主元素问题。只要每次都从数组中移除两个不相同的数值，

如果有出现的次数超过数组长度的一半的数，那么就是最后剩下来的那个。

最后再检验一次是否有这样的数。

代码：

1 class Solution { 2 public: 3     int MoreThanHalfNum_Solution(vector
     
       numbers) { 4         // 从数组中移除两个不相同的数值，如果有出现的次数超过数组长度的一半的数，那么就是最后剩下来的那个 5         int numSize = numbers.size(); 6         int candidate = 0;  // 候选数，可能是出现的次数超过数组长度的一半的数 7         int cnt = 0;    // 标记当前的候选数没被抵消的次数 8         for(int i = 0; i < numSize; i++) { 9             if(cnt == 0) candidate = numbers[i];    // 重选候选数10             if(candidate == numbers[i]) cnt++;  // 次数加111             else cnt--; // 次数减112         }13         cnt = 0;14         for(int i = 0; i < numSize; i++)    // 检验15             if(numbers[i] == candidate)16                 cnt++;17         if(cnt * 2 <= numSize) return 0;18         return candidate;19     }20 };