【剑指】38，求数组中出现次数超过一半的数字

小咪咪 2023-07-10 14:23 1阅读 0赞

**题目描述**  
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组\{1,2,3,2,2,2,5,4,2\}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。  
**思路**: 可以用哈希map做这题，将每个数字作为键值先赋值0，然后再遍历，遍历每一个值，同时对应的值+1，直到出现某一个键值大于size/2.

代码：

int MoreThanHalfNum_Solution(vector<int> numbers) { 
     map<int,int>times;
     int half=numbers.size()/2;
     for(int x:numbers)
     	times[x]=0;			//键值对初始化
    
    for(int x:numbers)
    { 
    	times[x]++;
    	if(times[x]>half)
    	{ res=x;
    	break;
    	}
    }
     return res;
     }

利用stl中的map（底层是红黑树）来维护了一个哈希表。

方法二：  
思路：利用stl标准库的算法sort排序，将数组排序，然后遍历数组，从第一个开始，如果后面的数和当前的数相同，times++，如果不同，判断当前的最大次数是否超过了size/2,超过就返回了。没超过就设置次数从1开始，  
最后判断最大次数和最后一次的次数，再和size/2相比较。

代码：

int MoreThanHalfNum_Solution(vector<int> numbers) { 
    	int half =numbers.size()/2;
    	if(!numbers.size())return half;
    	sort(numbers.begin(),numbers.end());	//the key
    	int times=0,val=numbers[0],maxtimes=1;
    	for(int x:numbers)
    	{ 
    		if(val==x)
    			{ times++；
    			if（times>half)
    				return val;
    			}
    		else
    		{ 
    		val=x;	
    		times=1;
    }
    		return 0;
    }
    }

> 基于sort