题目描述
给定一个大小为n的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在众数。
示例 1:
输入: [3,2,3]
输出: 3
示例 2:
输入: [2,2,1,1,1,2,2]
输出: 2
思路
其实可以使用反证法来论证这样得到的结果一定是众数，如果不是，则真正的众数一定被抵消掉了，如果把数组中的数分为两类：众数，其他数
最极端的情况，所有的其他数和众数发生抵消行为(因为也会发生其他数之间的抵消行为)，因为众数过半，所以到最后是抵消不完的，一定最后剩下的是众数，这与我们假设最终得到的是非众数发生矛盾。
摩尔投票法
说白了就是不同元素之间的抵消(可以直观的认为不同元素之间的抵消，符合交换律和结合律)，最后剩下的就是要求的目标，这里需要区分的是，摩尔算法不能确保得到的一定是众数（mode）(只有众数一定存在时摩尔算法得到的才是众数)，
例如数组：[1,1,1,2,2,3,3,4,4]，摩尔算法得出最后的结果应该是4，但4并不是众数，那是因为，大多数是指出现次数过半的数，而这个数组中没有这样的数，所以摩尔算法是是失效的，对于这种情况采取需要重新投票。
代码实现
class Solution {
public:
int majorityElement(vector<int>& nums) {
int n = nums.size();
int ret = -1;
int cnt = 0;
for(int i = 0;i < n;i++)//流式处理
{
if(cnt == 0)//流式处理，进来时先进行判断再决定要进行的操作
{
ret = nums[i];
cnt = 1;
}
else
{
if(nums[i] == ret)
cnt++;
else
cnt--;
}
}
return ret;
}
};