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

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。你可以假设数组是非空的，并且给定的数组总是存在多数元素。

方法1：数组排序：首先将 nums 排序，由于该数字超过数组长度的一半，所以数组的中间元素就是答案，时间复杂度为 O(nlogn),空间复杂度：O(1)

int MoreThanHalfNum_Solution(vector<int> numbers) 
{
	int len=numbers.size();	
	int res=len/2;//子数组超过原数组的一半，所以中间元素就是答案	
	sort(numbers.begin(),numbers.end());///用自带排序算法sort(first,last)进行排序
	return(numbers[res]);
    
}

方法2：哈希计数：遍历 nums 数组，将数字存在 HashMap 中，统计数字出现次数，统计完成后再遍历一次 HashMap，找到超过一半计数的数字，时间复杂度为 O(n),空间复杂度：O(n)

int MoreThanHalfNum_Solution(vector<int> numbers) 
{
    unordered_map<int,int> umap;//声明无序键值对容器 
    int count=numbers.size()/2;
	for(auto num:numbers)//auto表示根据后面赋值类型来确定数据类型 
		umap[num]++;
			
	for(auto num:numbers)
	{
		if(umap[num]>count)
		{
			return num;
		}
	}
	return -1;
		   
}

方法3：摩尔投票：时间复杂度为 O(n),空间复杂度：O(1)

/*
如果两个数不相等，就消去这两个数，最坏情况下，每次消去一个众数和一个非众数，那么如果存在众数，最后留下的数肯定是众数。

具体做法：

1.初始化：候选人cond = -1， 候选人的投票次数cnt = 0
2.遍历数组，如果cnt=0， 表示没有候选人，则选取当前数为候选人，++cnt
3.否则，如果cnt > 0, 表示有候选人，如果当前数=cond，则++cnt，否则--cnt
4.直到数组遍历完毕，最后检查cond是否为众数
*/

int MoreThanHalfNum_Solution(vector<int> numbers) 
{
    int cand=-1;
	int count=0;
	
	for(auto num:numbers)
	{
		if(count==0)
			cand=num;
		if(cand==num)
			count++;
		else
			count--;
				
	} 
	return cand;
    
}