给定 n n n个互不相同的数组成的集合 S S S以及正整数 k ≤ n k\leq n k≤n，试设计一个 O ( n ) \Omicron(n) O(n)时间算法找出 S S S中最接近 S S S的中位数的 k k k个数。

注意：此处“最接近”指数值大小接近，而不是排序位置接近。

若已知能在线性时间内找到数组中第 k k k小的元素的算法，求解步骤如下：

1.通过该算法求数组的中位数；

2.计算数组中每个元素与中位数之差的绝对值并存放在绝对值数组；

3.通过该算法求绝对值数组中第 k k k小的数；

4.将原数组中与中位数之差的绝对值小于等于第 k k k小的绝对值的元素输出即为答案。

（注意：该算法要求绝对值数组中的元素不重复）

能在线性时间内找到数组中第 k k k小的元素的算法在另一篇博客中已有介绍，此处不再赘述，参考链接：

算法分析与设计-线性时间选择详解（通俗易懂，含图解，附源码）（c++)__Eliuak_的博客-CSDN博客