题解 | #数组中出现次数超过一半的数字#

分析

一个数字出现的次数超过数组长度的一半<=>这个数字出现的次数可以抵消所有其它数字出现的次数

首先对elem=a[0]进行计数cnt=1, 当后面a[i]为elem时，就cnt++，否则cnt--，当cnt减为0时，从elem=a[i]重复前面的动作。

这样最终所求数字只可能是elem或者不存在。

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> vec) {
		if (vec.empty())
		{
			return 0;
		}
		
		int cnt = 1;
		int elem = vec[0];
		for (int i = 1; i < vec.size(); ++i)
		{
			if (vec[i] == elem)
			{
				cnt++;
			}
			else
			{
				cnt--;
				if (cnt == 0)
				{
					elem = vec[i];
					cnt = 1;
				}
			}
		}
		
		cnt = 0;		
		for (int i = 0; i < vec.size(); ++i)
		{
			if (vec[i] == elem)
			{
				cnt++;
			}
		}
		
		if (cnt > vec.size() / 2)
		{
			return elem;
		}
		
		return 0;	
    }
};