数组中出现次数超过一半的数字
C++，我也不知道考点算什么，模拟吧。
利用一个数学特点：
如果数组中一个数字出现的频次大于数组的一半长度，则出现频次会比其他数字的频次和还大；
定义两个整型变量，ans和cnt，前者表示当前记录的数字，后者是数字出现次数：
- ans = numbers[0]，cnt = 1，遍历整个序列；
- 如果碰到的数字和ans相同，cnt++；
- 如果碰到的数字和ans不同，cnt–；
- 如果cnt == 0，则将ans修改为当前所在位置的数字；
- 如果数组中存在这么“出现的频次大于数组的一半长度的数字”，那最后得到的ans一定就是这个数字；
为了避免最后不存在这个数字，还得检查是否ans出现的频次超过了一半。
代码：
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers) {
if (numbers.empty()) return 0;
int ans = numbers[0], cnt = 1;
for (int i = 1; i < numbers.size(); i++) {
if (ans == numbers[i])
cnt++;
else
cnt--;
if (cnt == 0) {
cnt = 1;
ans = numbers[i];
}
}
cnt = 0;
for (int &it : numbers)
cnt = it == ans ? cnt + 1 : cnt;
if (cnt > numbers.size() / 2)
return ans;
else return 0;
}
};
