題干：

描述

?

給你一個數(shù)組，輸出里面出現(xiàn)超過1/2的元素。保證有且只有一個解。

輸入

第一行是一個整數(shù)，表示測試數(shù)據(jù)的組數(shù) n，n < 1000萬 之后每一行都是一個整數(shù)。

輸出

輸出出現(xiàn)超過1/2的那個數(shù)字。

輸入樣例 1?

5 1 1 1 2 3

輸出樣例 1

1

提示

• 不要使用 cin，測試數(shù)據(jù)很大。

• 將時間復雜度降到 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); //}

?

總結(jié)

以上是生活随笔為你收集整理的【qduoj - 1011】数组中出现最多的元素（巧妙方法 或 排序 或 map）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。