题目描述

在一个含n个数的一维数组中，找出一点x距离所有数的距离和最近，并输出最近距离；
结论：如果n为奇数中位数为x，如为偶中间两数均可为x；
推导：在数轴上有两数a,b有x距离a，b的距离最短，x一定在a，b之间，所以|a-x|+|b-x|>=|a-b|。由此推论x在a1到an之间,a2-an-1……之间所以为中位数n/2。

算法1

排序+中位数

时间复杂度

O(n log n)

参考文献 yxc视频

#include<iostream>
#include<algorithm>
using namespace std;
int p[100010];
int n,s=0;
int main()
{
cin>>n;
for(int i=0;i<n;i++) cin>>p[i];

sort(p,p+n);

for(int i=0;i<n;i++) s+=abs(p[i]-p[n/2]);//可以改成s+=p[i]-p[i/2]；

cout<<s<<endl;
return 0;
}

算法2

快速选择+中位数

快速选择函数nth_element(数组初位置，寻找元素，数组末位置)

时间复杂度

O(n)

参考文献yxc视频

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;
int p[100010];
int main(){
int n,s=0;
cin>>n;
for(int i=0;i<n;i++) cin>>p[i];
nth_element(p,p+n/2,p+n);
for(int i=0;i<n;i++) s+=abs(p[i]-p[n/2]);
cout<<s<<endl;
return 0;
}