1.先找出S中的中位数的索引位置m，现在S[1...m-1]都小于S[m]，S[m+1....n]都大于S[m]，在S[1...m-1]中找第m-1-k个小的元素，S[m-k...m-1]都可能是最接近中位数的k个数。在S[m+1....n]中找地k个小的数，S[m+1...m+k]都可能是最接近中位数的k个数。
2.对找出的2k个元素构成一个新数组C。
3.对于C中每个元素都减去S的中位数，并取绝对值，构成新数组C'。
4.对于C'找出其中的第k个小的元素，则C'[1...k]就是最接近中位数的k个数。
Read full article from 9.3-7 - 算法导论习题解答
No comments:
Post a Comment