出现次数超过一半的数
2018-04-26 本文已影响30人
逍遥_9353
/*
出现次数超过一半的数
数组中有一个数出现的次数超过了数组长度的一半，找出这个数。
*/
/*
思路：
定义两个变量，一个用来保存数组中遍历的某个数，另一个用来表示
数组中当前数出现的次数，其中当前数出现的次数初始化为1，当遍历
到数组中下一个数的时候：如果下一个数与保存数组中遍历的某个数
相同时，则当前数出现的次数加1，否则减1。每当当前数出现的次数变
为0时，用来保存数组中的遍历的某个数就要保存下一个数，并把当前
出现的次数重新设置为1，直到遍历完整个数组为止。
*/
#include<iostream>
using namespace std;
int main()
{
int array[100],n,i,ntimes=1,candidate;
cin>>n;
for(i=0;i<n;i++)
cin>>array[i];
candidate=array[0];
for(i=1;i<n;i++)
{
if(ntimes==0)
{
candidate=array[i];
ntimes=1;
}
else
{
if(candidate==array[i])
ntimes++;
else
ntimes--;
}
}
cout<<candidate<<endl;
return 0;
}
