算法1
(模拟) $O(nlogn)$
直接模拟就好了 :
先对输入的a数组进行排序;
再判断n的奇偶 :
n 为 奇 : 输出a[n/2];
n 为 偶 : 输出( a[n/2-1] + a[n/2] ) / 2
时间复杂度
对于每组测试数据,使用了sort()函数,时间复杂度为O(nlogn),谢谢 @[胡尔大摩斯]的提醒!
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
int n,a[10010];
void solve(){
while(cin>>n){
if(n==0) break;
for(int i=0;i<n;i++) cin>>a[i];
sort(a,a+n);
if(n%2==0) cout<<(a[n/2-1]+a[n/2])/2<<endl;
else cout<<a[n/2]<<endl;
}
}
signed main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int T=1;
while(T--)solve();
}
你确定这是$o(n ^ 2)$?
每个题解本来的标签是O(n^2),我没有改,hhh,我现在去改下,谢谢提醒!!!