出现次数超过一半的数

/*

出现次数超过一半的数

    数组中有一个数出现的次数超过了数组长度的一半，找出这个数。

*/

/*

思路：

    定义两个变量，一个用来保存数组中遍历的某个数，另一个用来表示

数组中当前数出现的次数，其中当前数出现的次数初始化为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;

}