题干：

描述

 

给你一个数组，输出里面出现超过1/2的元素。保证有且只有一个解。

输入

第一行是一个整数，表示测试数据的组数 n，n < 1000万 之后每一行都是一个整数。

输出

输出出现超过1/2的那个数字。

输入样例 1 

5
1
1
1
2
3

输出样例 1

1

提示

  • 不要使用 cin，测试数据很大。
  • 将时间复杂度降到 O(n)

解题报告：

 

AC代码：（三种）

#include<cstdio>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<iostream>
#include<algorithm>
#define ll long long
#pragma GCC optimize(2)
const ll mod = 1e9+7;
using namespace std;
int n;
ll a[10000000 +5];
int main()
{
	int n,res;
	ll tmp;
	scanf("%d",&n);
	res = n/2+1;
	for(int i = 1; i<=n; i++) {
		scanf("%lld",&a[i]);
	}
	sort(a+1,a+n+1);
	printf("%lld",a[res]);
	
	
	return 0 ;
}
//#include<cstdio>
//#include<queue>
//#include<cstring>
//#include<cmath>
//#include<map>
//#include<iostream>
//#include<algorithm>
//#define ll long long
//const ll mod = 1e9+7;
//using namespace std;
//int n;
//ll a[10000000 +5];
//map<ll,int> mp;
//int main()
//{
//	int n,res;
//	ll tmp;
//	scanf("%d",&n);
//	res = n/2+1;
//	for(int i = 1; i<=n; i++) {
//		scanf("%lld",&tmp);
//		mp[tmp]++;
//	}
//	map<ll,int> :: iterator it;
//	for(it = mp.begin(); it!=mp.end(); ++it) {
//		if(it->second >= res) printf("%lld\n",it->first);
//	}
//	
//	return 0 ;
//}
//
//#include<bits/stdc++.h>
//using namespace std;
//int main()
//{
//    int n;
//    scanf("%d",&n);
//    int temp,time=0,a;
//    for(int i=0;i<n;i++)
//    {
//        scanf("%d",&a);
//        if(time==0)
//        {
//            time=1;
//            temp=a;
//        }
//        else if(temp==a)
//        {
//            time++;
//        }
//        else
//        {
//            time--;
//        }
//    }
//    printf("%d\n",temp);
//}