有 n 个整数, 其中有且仅有一个整数出现了 >= n/2.0 次 (n<=500000)

输入格式

每组数据第一行是 n, 然后接下来一行是 n 个整数, 请读入到 EOF

输出格式

输出每行一个整数, 即要找的这个数

样例输入

9
5 5 5 5 5 1 2 3 4

样例输出

5

#include<stdio.h>
#include<stdlib.h>
int num[500005];
int main(){  
    int n,i,j,t,ans,num1,num2;
    while(scanf("%d",&n) != EOF){
        j=0;
        for(i=0;i<n;i++){  
            scanf("%d",&num[i]);  
            if(j==0){  
                j++;
                ans=num[i];
            }
            else if(ans==num[i]) j++;
            else j--;
        }
        if(j>0)
            printf("%d\n",ans);
        else{
            t=num[n-1];
            num1=0;num2=0;
            for(i=0;i<n;i++){
                if(num[i]==ans)
                    num1++;
                else if(num[i]==t)
                    num2++;
            }
            if(num1>num2)
                printf("%d\n",ans);
            else
                printf("%d\n",t);
        }
    }
    return 0;
}