题目描述
中间数若存在,一定是排序后处在中间位置的一位数或者两位数
我们只需要判断它们就可以
这样时间复杂度就是nlogn
算法1
$O(n*logn)$
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int q[N];
int n;
int l,r;
int res=-1; //存储满足条件的数字
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&q[i]);
sort(q+1,q+n+1);
int x=q[n/2+1];
for(int i=1;i<=n;i++){
if(q[i]>x) l++;
if(q[i]<x) r++;
}
if(l==r)
res=q[n/2+1];
cout <<res<<endl;
return 0;
}
算法2
数据范围不大,可以暴力来做
(暴力枚举) $O(n^2)$
C++ 代码
#include<iostream>
using namespace std;
const int N=1010;
int q[N];
int n;
int l,r;
int temp; //存储每个遍历到要判断是否是中间数的数字
int res=-1; //存储满足条件的数字
int main(){
cin >>n;
for(int i=1;i<=n;i++)
cin >>q[i];
for(int i=1;i<=n;i++){
temp=q[i];
for(int i=1;i<=n;i++){
if(q[i]>temp) l++;
if(q[i]<temp) r++;
}
if(l==r) res=q[i];
r=0,l=0;
}
cout <<res<<endl;
return 0;
}
算法3
$O(n*logn)$
参考文献
y总讲的快排模板
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int q[N];
int n;
int l,r;
int res=-1; //存储满足条件的数字
void quick_sort(int q[], int l, int r)
{
if (l >= r) return;
int i = l - 1, j = r + 1, x = q[l + r >> 1];
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
quick_sort(q, l, j), quick_sort(q, j + 1, r);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&q[i]);
quick_sort(q,1,n);
int x=q[n/2+1];
for(int i=1;i<=n;i++){
if(q[i]>x) l++;
if(q[i]<x) r++;
}
if(l==r)
res=q[n/2+1];
cout <<res<<endl;
return 0;
}