在白书中提到了一种O（n)级别的寻找中位数算法 就是我们今天要介绍的主角
快速选择算法
类似快排 选择一个比较元素 进行递归处理寻找第k大元素
假设最后比较元素到了i
以下描述是我写快排的常用字符 所以外人应该看不懂。。。。
如果(i-s+1)<k 去（i+1,t)的区间 递归寻找第（k-（i-s+1)) 大的数
如果（i-s+1）=k 返还i的值即可
如果 （i-s+1）>k 去 （s,i-1)的区间 递归找第k大的数
类似快排的思想 很容易理解
代码如下：
int swap(long long &a,long long &b) {long long temp=a;a=b;b=temp;return 0;}
int quickchoice(long long *A,int s,int t,int k)
{
int i=s,j=t;
long long x=A[s];
while(i<j)
{
while(i<j&&A[j]>=x) j--;
if(i<j) swap(A[i],A[j]),i++;
while(i<j&&A[i]<x) i++;
if(i<j) swap(A[j],A[i]),j--;
}
A[i]=x;
if((i-s+1)==k) return 0;
else if((i-s+1)<k&&i+1<=t) quickchoice(A,i+1,t,k-(i-s+1));
else if((i-s+1)>k&&s<=i-1) quickchoice(A,s,i-1,k);
return 0;
}
UVA11300快速选择算法实现如下：
#include<cstdio>
#include<cmath>
#include<cstdlib>
using namespace std;
long long gold[1000100],M;
int cmp(const void *i,const void *j)
{
if(*(long long *)i>*(long long *)j) return 1;
else if(* (long long *)i==*(long long *)j) return 0;
else return -1;
}
int main()
{
int n,k;
long long sum;
while(scanf("%d",&n)!=EOF)
{
sum=0;
for(int i=1;i<=n;i++)
{
scanf("%lld",&gold[i]);
sum+=gold[i];
}
M=sum/n;
for(int i=1;i<=n-1;i++)
gold[i]=gold[i-1]+M-gold[i];
gold[n]=0;
qsort(gold+1,n,sizeof(gold[1]),cmp);
k=(n+1)/2;
sum=0;
for(int i=1;i<=n;i++)
sum=sum+abs(gold[i]-gold[k]);
printf("%lld\n",sum);
}
return 0;
}
上面这个方法不知道为何 速度和快排没什么区别。。
但是下面这个就快了一倍
nth_element函数 非常奇怪
好吧 觉得奇怪 是被网上各种奇葩的资料误导了
自己亲手操作后还是懂了
nth_element(begin,kth,end)
在[begin，end)这段区间内找第k大的数 其实这样描述是不精确的
这样描述似乎更合适
比如 nth_element(s+1,s+k,s+n+1)
在[1,n+1)这段区间内 s[k] 左边的全部小于等于他 右边的全部大于等于他
如果 区间从1开始 似乎确实可以描述成 第k个
如果不从1开始就注意点
AC代码如下：
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;
long long gold[1000100],M;
int n;
int main()
{
int k;
long long sum;
while(scanf("%d",&n)!=EOF)
{
sum=0;
for(int i=1;i<=n;i++)
{
scanf("%lld",&gold[i]);
sum+=gold[i];
}
M=sum/n;
for(int i=1;i<=n-1;i++)
gold[i]=gold[i-1]+M-gold[i];
gold[n]=0;
k=(n+1)/2;
nth_element(gold+1,gold+k,gold+1+n);
for(int i=1;i<=n;i++)
printf("gold:%d\n",gold[i]);
sum=0;
for(int i=1;i<=n;i++)
sum=sum+abs(gold[i]-gold[k]);
printf("%lld\n",sum);
}
return 0;
}