在O(n)时间范围内找出数组a[n]中位数相邻的k个数字
思路:简单的思路是先找出中位数(n+1)/2然后依次找第(n+1)/2-1小数字、(n+1)/2-2小数字、(n+1)/2-3.小数字。。。。(n+1)/2-k/2小数字,再找第(n+1)/2+1小数字、(n+1)/2+2小数字、(n+1)/2+3.小数字。。。。(n+1)/2+(k+1)/2小数字。但是该算法时间复杂度为O(kn)。
改进思路为:先找中位数,将数组按照中位数进行分割,数组的前半部分找第(n-1)/2-k/2小的数字,按照该数字对前半部分进行分割,则该数字到中位数之前的数字有k/2个数字,这些数字为与中位数相邻且小于中位数的前k/2个数字。数组的后半部分找出第(k+1)/2小的数字,然后按照该元素对后半部分进行分割,则中位数后一元素到该元素的(k+1)/2个元素为与中位数相邻且大于中位数的数字。该算法共调用三次分割选择函数Select,而该函数的时间复杂度为O(n),所以时间复杂度为O(n)。其具体代码如下:
//例题9.2中的算法的期望时间复杂度为O(n),而在9.3的例题中的最坏运行时间复杂度为O(n)。 //该算法实现思路是将数组每五个元素分为一组,最后一组可能不足五个。 //选出每一组中的中位数,然后选出这些中位数的中位数。根据这个中位数对数组进行划分为两组。 //然后再按照9.。2中的方法递归调用划分寻找第i小的数。 //该算法的对比于9.2的改进之处在于对partition方法进行了优化,而不是随进选择数组进行划分。 #include<iostream> using namespace std; //插入排序不解释 void Insert_sort(int a[],int p,int r) { int i,j,key,length; length=r-p+1; for(i=p+1;i<=r;i++) { key=a[i]; j=i-1; while(key<a[j]) { int temp; temp=a[j+1]; a[j+1]=a[j]; a[j]=temp; j=j-1; if(j<p) { break; } } } } //按照中位数的中位数进行分割 int Partition(int a[] ,int p,int r) { int i=p,j=0,temp,num,b[100]; //将a中每五个元素进行插入排序,并找出五个元素中的中位数放到b中 while(1) { if(i>r) { break; } if((i+4)<=r) { Insert_sort(a,i,i+4); b[j++]=a[i+2]; } else { Insert_sort(a,i,r); b[j++]=a[(r+i)/2]; } i+=5; } j=j-1; //对b中的元素进行排序 Insert_sort(b,0,j); //找到b中的中位数 num=b[j/2]; //将a中的num与a[r]替换 for(i=0;i<=r;i++) { if(num==a[i]) break; } temp=a[i]; a[i]=a[r]; a[r]=temp; //根据找到的num对数组进行划分 j=p-1; for(i=p;i<r;i++) { if(a[i]<num) { j++; temp=a[i]; a[i]=a[j]; a[j]=temp; } } temp=a[r]; a[r]=a[j+1]; a[j+1]=temp; return j+1; } //按照特定的数字num进行分割 int Partition1(int a[] ,int p,int r,int num) { int i,j=0,temp; //将a中每五个元素进行插入排序,并找出五个元素中的中位数放到b中 //将a中的num与a[r]替换 for(i=0;i<=r;i++) { if(num==a[i]) break; } temp=a[i]; a[i]=a[r]; a[r]=temp; //根据找到的num对数组进行划分 j=p-1; for(i=p;i<r;i++) { if(a[i]<num) { j++; temp=a[i]; a[i]=a[j]; a[j]=temp; } } temp=a[r]; a[r]=a[j+1]; a[j+1]=temp; return j+1; } //选择第num小的数字 int Select(int a[],int p,int r,int num) { if(p==r) { return a[p]; } int q=Partition(a,p,r); int k=q-p+1; if(k==num) { return a[q]; } else if(num<k) { return Select(a,p,q-1,num); } else { return Select(a,q+1,r,num-k); } } void SelectKthNearTheMiddle(int a[],int b[],int p,int r,int k) { int i,j; if(k<=0) { cout<<"wrong number!"<<endl; return ; } int length,t,s,q; length=r-p+1; //找出中位数为第(length+1)/2小的数字 s=Select(a,p,r,(length+1)/2); //本来打算调用Partition1将数组从s值处分割为两部分 //调试时发现该步骤 是多余的,因为在Select(a,p,r,(length+1)/2)中已经 //把数组按照s分割为两部分了,下面调用的两Select跟此处的一样,不用再调用Partition1 //Partition1(a,p,r,s); //在中位数之前的数组中找出第(length-1)/2-(k)/2+1的元素 //该元素到中位数之前的数字为接近中位数的k/2个数字 t=Select(a,p,p+(length-1)/2-1,(length-1)/2-(k)/2+1); //找出中位数之后数组中第(k+1)/2小的元素,中位数之后起的第一个数字到该元素为 //接近中位数的(k+1)/2个数字 q=Select(a,p+(length-1)/2+1,r,(k+1)/2); //将中位数元素前一个元素到t赋给数组b的前半部分,此复制为倒序,所以j是从(k)/2-1开始到0的 j=(k)/2-1; for(i=p+(length-1)/2-1;i>=p+(length-1)/2-(k)/2;i--) { b[j--]=a[i]; } //将中位数元素后一个元素到q赋给b的后半部分 j=(k)/2; for(i=p+(length-1)/2+1;i<=p+(length-1)/2+(k+1)/2;i++) { b[j++]=a[i]; } } int main() { int a[15]={16,48,748,742,1635,2,56,48,685,4596,3,4,1,6,5}; int b[100]; SelectKthNearTheMiddle(a,b,0,14,5); for(int i=0;i<5;i++) { cout<<b[i]<<" "; } cout<<endl; return 0; }