“OK, you are not too bad, em… But you can never pass the next test.” feng5166 says.
“I will tell you an odd number N, and then N integers. There will be a special integer among them, you have to tell me which integer is the special one after I tell you all the integers.” feng5166 says.
“But what is the characteristic of the special integer?” Ignatius asks.
“The integer will appear at least (N+1)/2 times. If you can’t find the right integer, I will kill the Princess, and you will be my dinner, too. Hahahaha…..” feng5166 says.
Can you find the special integer for Ignatius?
Input
The input contains several test cases. Each test case contains two lines. The first line consists of an odd integer N(1<=N<=999999) which indicate the number of the integers feng5166 will tell our hero. The second line contains the N integers. The input is terminated by the end of file.
Output
For each test case, you have to output only one line which contains the special number you have found.
Sample Input
5
1 3 2 3 3
11
1 1 1 1 1 5 5 5 5 5 5
7
1 1 1 1 1 1 1
Sample Output
3
5
1
题目大意：给定一个整数N，然后给出N个整数，统计出现次数最多的那个数并输出。
思路：见代码。
#include<iostream>
#include<cstring>
#include<stdio.h>
#include<queue>
#include<stdlib.h>
#include<algorithm>
using namespace std;
const int MAX=1000009;
int n,ans,A[MAX];
//题目不难，有思路，可以排序(会超时)等
//但他应付不了强数据，所以要找出好的想法来
//排序法----------------------超时
//计数排序
void f1(){
memset(A,0,sizeof(A));
for(int i=0 ; i<n ; i++){
cin>>ans;
A[ans]++;
if(A[ans] == (n+1)/2){
cout<<ans<<endl;
}
}
return;
}
//自带排序
void f2(){
memset(A,0,sizeof(A));
for(int i=0 ; i<n ; i++){
cin>>A[i];
}
sort(A,A+n);
cout<<A[(n+1)/2]<<endl;
return;
}
//不用排序
//由于该数字的出现次数比所有其他数字出现次数的和还要多
//所以可以在遍历数组时保存两个值：一个是数组中的一个数字，一个是次数
//当遍历到下一个数字时，如果下一个数字与之前保存的数字相同，则次数加1
//如果不同，则次数减1，如果次数为0，则需要重新保存下一个数字，并把次数设定为1
//因为要找的数字出现的次数比其他所有数字的出现次数之和还要大
//故要找的数字肯定是最后一次把次数设为1时对应的数字
void f3(){
int cnt=0;
for(int i=0 ; i<n ; i++){
cin>>A[i];
if(0 == cnt){
ans = A[i];
cnt = 1;
}else if(A[i] == ans){
cnt++;
}else{
cnt--;
}
}
cout<<ans<<endl;
return;
}
int main(void){
while(scanf("%d",&n)!=EOF){
f1();
// f2();
// f3();
}
return 0;
}