算法导论9.37

题目：

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

思考：

step1：求出数组的中位数的值O(n)

step2：计算数组每个数与中位数差的绝对值，存于另一个数组B中O(n)

step3：求出数组B中第k小的数ret O(n)

step4：计算数组S中与ret差的绝对值小于ret的数并输出O(n)

其中，step4也可以通过划分的方法找出数组S中与ret差的绝对值小于ret的数

代码：

  1 #include <iostream>
  2 using namespace std;
  3 
  4 int length_A;
  5 void Print(int *A)
  6 {
  7     int i;
  8     for(i = 1; i <= length_A; i++)
  9         cout<<A[i]<<' ';
 10     cout<<endl;
 11 }
 12 /*************最坏情况线性时间的选择**************************************************/
 13 //已经出现很多次了，不解释
 14 int Partition(int *A, int p, int r)
 15 {
 16     int x = A[r], i = p-1, j;
 17     for(j = p; j < r; j++)
 18     {
 19         if(A[j] <= x)
 20         {
 21             i++;
 22             swap(A[i], A[j]);
 23         }
 24     }
 25     swap(A[i+1], A[r]);
 26     return i+1;
 27 }
 28 int Select(int *A, int p, int r, int i);
 29 //对每一组从start到end进行插入排序，并返回中值
 30 //插入排序很简单，不解释
 31 int Insert(int *A, int start, int end, int k)
 32 {
 33     int i, j;
 34     for(i = 2; i <= end; i++)
 35     {
 36         int t = A[i];
 37         for(j = i; j >= start; j--)
 38         {
 39             if(j == start)
 40                 A[j] = t;
 41             else if(A[j-1] > t)
 42                 A[j] = A[j-1];
 43             else
 44             {
 45                 A[j] = t;
 46                 break;
 47             }
 48         }
 49     }
 50     return A[start+k-1];
 51 }
 52 //根据文中的算法，找到中值的中值
 53 int Find(int *A, int p, int r)
 54 {
 55     int i, j = 0;
 56     int start, end, len = r - p + 1;
 57     int *B = new int[len/5+1];
 58     //每5个元素一组，长度为start到end，对每一组进行插入排序，并返回中值
 59     for(i = 1; i <= len; i++)
 60     {
 61         if(i % 5 == 1)
 62             start = i+p-1;
 63         if(i % 5 == 0 || i == len)
 64         {
 65             j++;
 66             end = i+p-1;
 67             //对每一组从start到end进行插入排序，并返回中值,如果是最后一组，组中元素个数可能少于5
 68             int ret = Insert(A, start, end, (end-start)/2+1);
 69             //把每一组的中值挑出来形成一个新的数组
 70             B[j] = ret;    
 71         }
 72     }
 73     //对这个数组以递归调用Select()的方式寻找中值
 74     int ret = Select(B, 1, j, (j+1)/2);
 75     //delete []B;
 76     return ret;
 77 }
 78 //以f为主元的划分
 79 int Partition2(int *A, int p, int r, int f)
 80 {
 81     int i;
 82     //找到f的位置并让它与A[r]交换
 83     for(i = p; i < r; i++)
 84     {
 85         if(A[i] == f)
 86         {
 87             swap(A[i], A[r]);
 88             break;
 89         }
 90     }
 91     return Partition(A, p, r);
 92 }
 93 //寻找数组A[p..r]中的第i大的元素，i是从1开始计数，不是从p开始
 94 int Select(int *A, int p, int r, int i)
 95 {
 96     //如果数组中只有一个元素，则直接返回
 97     if(p == r)
 98         return A[p];
 99     //根据文中的算法，找到中值的中值
100     int f = Find(A, p, r);
101     //以这个中值为主元的划分，返回中值在整个数组A[1..len]的位置
102     //因为主元是数组中的某个元素，划分好是这样的，A[p..q-1] <= f < A[q+1..r]
103     int q = Partition2(A, p, r, f);
104     //转换为中值在在数组A[p..r]中的位置
105     int k = q - p + 1;
106     //与所寻找的元素相比较
107     if(i == k)
108         return A[q];
109     else if(i < k)
110         return Select(A, p, q-1, i);
111     else
112         //如果主元是数组中的某个元素，后面一半要这样写
113         return Select(A, q+1, r, i-k);
114         //但是如果主元不是数组中的个某个元素，后面一半要改成Select(A, q, r, i-k+1)
115 }
116 int main()
117 {
118     int k, i;
119     while(cin>>length_A>>k)
120     {
121         if(k > length_A)
122         {
123             cout<<"error:k > length_A"<<endl;
124             continue;
125         }
126         //生成随机数据
127         int *A = new int[length_A+1];
128         for(i = 1; i <= length_A; i++)
129             A[i] = rand() % 100;
130         Print(A);
131         //计算中位数
132         int mid = Select(A, 1, length_A, (length_A+1)/2);
133         //计算每个数与中位数的距离
134         int *B = new int[length_A+1];
135         for(i = 1; i <= length_A; i++)
136             B[i] = abs(A[i] - mid);
137         //选择第k小的数
138         int ret = Select(B, 1, length_A, k);
139         //求出数组是与中位数距离小于ret的数，并输出
140         for(i = 1; i <= length_A; i++)
141             if(abs(A[i] - mid) <= ret)
142                 cout<<A[i]<<' ';
143         cout<<endl;
144         delete []A;
145     }
146     return 0;
147 }