题目描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
方法一：
#include <iostream>
#include <vector>
#include <map>
using namespace std;
int MoreThanHalfNum_Solution(vector<int> numbers){
map<int,int> countMap;
int s=numbers.size();
for(int i=0;i<s;i++)
countMap[numbers[i]]++;
int r;
int maplen=countMap.size();
map<int,int>::iterator it;
for(it=countMap.begin();it!=countMap.end();it++){
if(it->second>s/2){
r=it->first;
return r;
}
}
return 0;
}
int main(){
int a[9]={1,2,3,2,2,2,5,4,2};
vector<int> numbers(a,a+9);
MoreThanHalfNum_Solution(numbers);
system("pause");
}
方法二：
#include <iostream>
#include <vector>
using namespace std;
int MoreThanHalfNum_Solution(vector<int> numbers){
int count=1;
int num=numbers.front();
for(int i=1;i<numbers.size();i++){
if(num!=numbers[i]){
count--;
if(count==0){
count=1;
num=numbers[i];
}
}else
count++;
}
if(count>=1){
int s=0;
for(int i=0;i<numbers.size();i++){
if(num==numbers[i])
s++;
}
if(s>numbers.size()/2)
return num;
else return 0;
}else
return 0;
}