找出集合S最接近中位数的k(k≤n)个数

相关问题：

给出一个O(n)时间的算法，在给定一个有n个不同数字的集合S以及一个正整数k≤n后，它能确定出S中最接近其中位数的k个数.

思考过程：

如果给出在线性时间内的算法，那么可能要用到最坏为线性时间的查找第i小元素的子程序SELECT。我们先找到这n个数的中位数，然后以此中位数为中心，左边距离中位数k/2个远的位置是这k个数的左端点，右边距离中位数k/2个远的位置是这k个数的右端点。用SELECT函数找到这三个数（中位数，左边距离中位数k/2的数，右边距离中位数k/2的数）就可以确定最接近其中位数的k个数.。

PS：在网上这个问题没有用到这种方法。所以这种方法的正确性有待各位大牛来验证。如果有错误，请各位大牛留言指正哦。谢谢啦！

具体步骤：

step 1：用SELECT函数找到中位数，找到的同时也对数组进行了划分（step123都是根据《算法导论》9.3-4题目的结论，有兴趣可以看这篇博文），小于中位数的在左边，大于的在右边。

step 2：用SELECT函数找到左边距离中位数k/2的数，(注意不要对整个数组进行SELECT函数查找，要对中位数左半区域进行SELECT函数查找。)

step 3：按照step2方法对中位数的右半区进行查找。

以上三步都是通过SELECT函数来对数组划分使其最接近中位数的k个数聚集在中位数附近。并且每次调用SELECT函数只需要线性时间O(n)，所以总的过程也只需要线性时间。

[cpp] view plaincopyprint?

1. //显示中位数附近k个数。  
2. #include <iostream>  
3. #include <time.h>  
4. using namespace std;  
5. const n=24;  
6. //创建一个装有数组A以每5个元素为1组共n/5组，每组的中位数放入到数组B中，组成一组含有n/5个中位数的数组B  
7. int Find(int A[n],int p,int r);//递归当前数组A中从p到r个元素，以找到辅助中位数数组B的中位数。  
8. int PARTITION(int A[],int p,int r,int t)//t代表中位数数组B中的中位数，这里t代表为主元。  
9. {  
10.     int i=p-1,k=0;  
11.     for (int j=p;j<=r;j++)  
12.     {  
13.         if (A[j]<t)//将比主元t大的元素交换到数组A的右边去，比主元t小的到数组A的左边。  
14.         {  
15.             i++;  
16.             swap(A[i],A[j]);  
17.         }  
18.         if (A[j]==t)//如果A[j]等于主元  
19.         {  
20.             k=j;//那么记录下主元在A中的位置。  
21.         }  
22.     }  
23.     swap(A[i+1],A[k]);//完成划分操作，主元左边的元素都小于主元，主元右边的元素都大于主元。  
24.     return i+1;  
25. }  
26. int SELECT(int A[],int p,int r,int i)//i表示第i小的数。  
27. {  
28.     if (p>=r)  
29.     {  
30.         return A[p];  
31.     }  
32.     int t=Find(A,p,r);//返回的t代表辅助数组B的中位数。      
33.     int q=PARTITION(A,p,r,t);  
34.     int k=q-p+1;  
35.     if (i==k)  
36.     {  
37.         return A[q];  
38.     }  
39.     else if(i<k)  
40.     {  
41.         return SELECT(A,p,q-1,i);  
42.     }  
43.     else return SELECT(A,q+1,r,i-k);  
44. }  
45. int Find(int A[n],int p,int r)  
46. {      
47.     int key=0,t=0,m=r-p+1,h=0;  
48.     if (m%5==0)//如果当前数组A的大小能被5整除，那么这以5个元素为一组的m/5组数，没有余数那一组  
49.     {  
50.         h=m/5;  
51.     }  
52.     else//否则，应该加上含有余数的那一组。  
53.     {  
54.         h=m/5+1;  
55.      }  
56.     int *B=new int[h];  
57.     for(int j=0;j<h;j++)  
58.     {  
59.         B[j]=0;  
60.     }  
61.     for (int k=0;k<h;k++)//5个数一组，共h组。进行插入排序。  
62.     {//经过最多h=n/5+1次循环，那么总共循环了25h=25(n/5+1)=5n+25=O(n)次  
63.         for (int j=t+1+p;j<=5+t+p&&j!=r+2;j++)//h组中每组进行插入排序。注意加上数组初始坐标p(当前数组A的初值坐标)+t(在p基础上每5个为1组)  
64.         {//运行时间分析：5个一组运行插入排序，每次插入排序需要的时间是O(n^2)=5^2=25是基于固定划分的固定常数  
65.             key=A[j-1];  
66.             int i=j-1;  
67.             while (i>t+p&&A[i-1]<key)  
68.             {  
69.                 A[i]=A[i-1];  
70.                 i=i-1;  
71.             }  
72.             A[i]=key;  
73.         }  
74.         t+=5;//进入下一个5个元素为一组的插入排序  
75.     }  
76.     k=0;  
77.     for (int i=0;i<h&&k<h;i++)//经过最多h=n/5+1次循环(O(n))，将当前数组A中的每组的中位数依次放入到B中  
78.     {  
79.         if (i<h-1)  
80.         {  
81.             B[k]=A[2+5*i+p];  
82.             k++;  
83.             continue;  
84.         }  
85.         if(m%5!=0)  
86.         {  
87.             B[k]=A[5*i+p+(m%5)/2];  
88.         }  
89.         else   
90.         {  
91.             B[k]=A[2+5*i+p];  
92.             k++;  
93.         }  
94.     }  
95.     if (h==1)  
96.     {  
97.        return B[0];//当辅助数组B只剩下一个数时，那么这个数就是中位数的中位数。  
98.     }  
99.     else  
100.     {  
101.        return SELECT(B,0,h-1,(h-1)/2+1);//如果数组B元素个数是偶数，那么取数组B中的较小值。  
102.     }  
103. }  
104. void Close_median_number_of_k(int A[],int p,int r,int k)//接近中位数的k个数  
105. {  
106.      int i=(p+r+2)/2;  
107.      SELECT(A,p,r,i);//找到当前数组从p到r的中位数。  
108.      SELECT(A,p,i-1,i-k/2);//找到当前数组从p到i-1的第i-k/2个数。  
109.      SELECT(A,i,r,k/2);//找到当前数组从i到r的第k/2个数。  
110. }  
111. void Print(int A[],int start,int end)  
112. {  
113.     for (int i=start;i<end;i++)  
114.     {  
115.          cout<<A[i]<<" ";  
116.     }  
117.     cout<<endl;  
118. }  
119. void main()  
120. {  
121.     int A[n]={0};  
122.     //随机输入数组  
123.     srand( (unsigned)time( NULL ) );  
124.     cout<<"随机数组初始化。。。"<<endl;  
125.     for (int i=0;i<n;i++)  
126.     {  
127.         A[i]=rand()%100;  
128.         cout<<A[i]<<"\t";  
129.     }  
130.     cout<<endl;  
131.     int k;  
132.     cout<<"请输入需要查找的中位数附近多少个数？"<<endl;  
133.     cin>>k;  
134.     Close_median_number_of_k(A,0,n-1,k);  
135.     int h=(n-1)/2-k/2;//h代表中位数附近的k个数的第一个值的下标。  
136.     if (k%2==0)  
137.     {  
138.         h=h+1;//如果k为偶数，那么对初值做微调使其更接近中位数附近的k个数  
139.     }  
140.     cout<<"数组中位数附近的"<<k<<"个数"<<endl;  
141.     Print(A,h,h+k);//打印这k个数。  
142. }