算法导论第九章9.3.7----最接近中位数的k个数 - liken的专栏 - 博客频道 - CSDN.NET
Describe an O(n) algorithm that, given a set S of n distinct numbers
and a positive integer k ≤ n, determines the k numbers in S that are closest to the
median of S .
Solution:
Note that the k numbers in S that are closest to the median are among the k smallest numbers on either side of the partition (around the median).
注意到数组中最接近中位数的k个数字是两边分区中最小的k个数。
We first use linear time selection to find the median.
首先使用线性选择算法找到中位数。
Then we compute an array B of absolute differences between the ith element in S and the median, B[i] = |S [i] − median|.
之后计算数字B,该数组记录数组S中每个元素到中位数距离的绝对值。B[i] = |S [i] − median|.
The k elements closest to the median are the k smallest elements in B.
最接近中位数的k个元素是B中最小的k个元素。
We use linear time selection to find the k-th smallest element in B.
使用线性选择算法找到数组B中第k个最小元素。
The first k elements in the resulting partition of B correspond to the k numbers in S closest to the median.
数组B经过选择算法处理后,在结果划分的前k个元素就对应数组S中距离中位数最近的k个数。
The algorithm takes O(n) time as we use linear time selection exactly two times and traverse the n numbers in S once.
使用两次线性时间选择算法找中位数和第k个数,一次遍历数组S中的n个数,该算法时间复杂度为O(n)。
1 get the median of S
2 compute the distence of S to the median, store in B
3 get the kth order statistics in B. the first k elements in partition of B is the output
1: procedure k_Closest(S, k) //S: a set of n numbers and k: an integer
2: Output = nothing;
3: m = Select(S, n,n/2) //O(n)
4: for all s in S and s != m //O(n)
5: s.distance = |m − s|
6: end for
7: md = Select(S.distance, k) //O(n)
8: for all s in S
9: if s.distance <= md.distance then //O(n)
10: Output = Output + s
11: end if
12: end for
13: return Output
14: end procedure
Read full article from 算法导论第九章9.3.7----最接近中位数的k个数 - liken的专栏 - 博客频道 - CSDN.NET
Describe an O(n) algorithm that, given a set S of n distinct numbers
and a positive integer k ≤ n, determines the k numbers in S that are closest to the
median of S .
用O(n)找到中位数,然后每个数都减去中位数并且取绝对值,得到一个新数组,然后,找出新数组里的最小的k个数,也是花费O(n),所以最后的时间复杂度还是O(n)
Solution:
Note that the k numbers in S that are closest to the median are among the k smallest numbers on either side of the partition (around the median).
注意到数组中最接近中位数的k个数字是两边分区中最小的k个数。
We first use linear time selection to find the median.
首先使用线性选择算法找到中位数。
Then we compute an array B of absolute differences between the ith element in S and the median, B[i] = |S [i] − median|.
之后计算数字B,该数组记录数组S中每个元素到中位数距离的绝对值。B[i] = |S [i] − median|.
The k elements closest to the median are the k smallest elements in B.
最接近中位数的k个元素是B中最小的k个元素。
We use linear time selection to find the k-th smallest element in B.
使用线性选择算法找到数组B中第k个最小元素。
The first k elements in the resulting partition of B correspond to the k numbers in S closest to the median.
数组B经过选择算法处理后,在结果划分的前k个元素就对应数组S中距离中位数最近的k个数。
The algorithm takes O(n) time as we use linear time selection exactly two times and traverse the n numbers in S once.
使用两次线性时间选择算法找中位数和第k个数,一次遍历数组S中的n个数,该算法时间复杂度为O(n)。
1 get the median of S
2 compute the distence of S to the median, store in B
3 get the kth order statistics in B. the first k elements in partition of B is the output
- We find the median of the array in linear time
- We find the distance of each other element to the median in linear time
- We find the
k -th order statistic of the distance, again, in linear time - We select only the elements that have distance lower than or equal to the
k -th order statistic
1: procedure k_Closest(S, k) //S: a set of n numbers and k: an integer
2: Output = nothing;
3: m = Select(S, n,n/2) //O(n)
4: for all s in S and s != m //O(n)
5: s.distance = |m − s|
6: end for
7: md = Select(S.distance, k) //O(n)
8: for all s in S
9: if s.distance <= md.distance then //O(n)
10: Output = Output + s
11: end if
12: end for
13: return Output
14: end procedure
- /******寻找最接近中位数的k个数*******/
- //length:数组的长度
- void FindKNums(int a[], int length, int k)
- {
- if(k > length)
- {
- return;
- }
- //step1:求出数组的中位数的值O(n)
- int mid = Select(a, 0, length - 1, length / 2);
- cout << "mid = " << mid << endl;
- //step2:计算数组每个数与中位数差的绝对值,存于另一个数组B中O(n)
- int *b = (int *)malloc(sizeof(int) * length);
- if(b == NULL)
- {
- return;
- }
- for(int i = 0; i < length; i++)
- {
- b[i] = (int)fabs(double(a[i] - mid));
- }
- //step3:求出数组B中第k小的数ret O(n)
- int ret = Select(b, 0, length - 1, k);
- cout << "ret = " << ret << endl;
- //step4:计算数组S中与中位数的差的绝对值小于ret的数并输出O(n)
- for(int i = 0; i < length; i++)
- {
- int tmp = (int)fabs(double(a[i] - mid));
- if(tmp <= ret)
- {
- cout << a[i] << " ";
- }
- }
- cout << endl;
- }
Read full article from 算法导论第九章9.3.7----最接近中位数的k个数 - liken的专栏 - 博客频道 - CSDN.NET