题目描述 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
算法：计数，分组数据结构：数组编程语言：C++ 解法1：根据数组的特点，进行计数，出现次数最多的数字，如果超过数组长度的一半儿 就是最终的结果 class Solution { public: int MoreThanHalfNum_Solution(vector<int> numbers) { if(numbers.empty())//输入合法性判断 return 0; int result=numbers[0];//初始化返回值 //设定标志 遍历数组中的一个数字，把这个数字的出现次数设为1，继续遍历下一个数字，如果这个数字和它相同 //times的数字+1，如果不相同就-1，如果数字减为0，把下个数字作为参考数字，最后一个参考数字就是次数最多的数字 int times=1; for(int i=0;i<numbers.size();i++) { if(times==0)//设定新的参考数字 result=numbers[i]; else if(result==numbers[i]) times++; else times--; } //求出出现次数最的数字的出现次数 int count=0; for(int i=0;i<numbers.size();i++) { if(numbers[i]==result) count++; } //长度判定 if(count>(numbers.size()/2)) return result; else return 0; } };解法2：
class Solution { public: int MoreThanHalfNum_Solution(vector<int> numbers) { if(numbers.empty()) return 0; int length=numbers.size(); int mid=length>>1; int start=0; int end=length-1; int index=Partition(numbers,length,start,end); while(index!=mid) { if(index>mid) { end=index-1; index=Partition(numbers,length,start,end); } else { start=index+1; index=Partition(numbers,length,start,end); } } if(!MoreThanHalf(numbers,length,numbers[mid])) return 0; return numbers[mid]; } bool MoreThanHalf(vector<int>numbers,int length,int mid) { if(numbers.empty()) return false; int times=0; for(int i=0;i<numbers.size();i++) { if(numbers[i]==mid) times++; } if(times>(length>>1)) return true; return false; } int Partition(vector<int> &data,int length,int start,int end) { if(data.empty()||end>=length||start<0) return -1; int index=start; swap(&data[index],&data[end]); int small=start-1; for(index=start;index<=end;index++) { if(data[index]<data[end]) { ++small; if(data[small]!=data[index]) swap(&data[index],&data[small]); } } ++small; swap(&data[small],&data[end]); return small; } //交换两个元素 void swap(int *a,int *b) { int temp; temp=*a; *a=*b; *b=temp; } };