剑指Offer——数组中出现次数超过一半的数字

题目描述：

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

分析：

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

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

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

代码：

 1 class Solution {
 2 public:
 3     int MoreThanHalfNum_Solution(vector<int> 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++;  // 次数加1
11             else cnt--; // 次数减1
12         }
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 };