以中位数为基准的选择问题

问题描述：给定一个由n个互不相同的数组成的集合S，以及一个正整数k<=n，设计一个O(n)时间的算法找到S中最接近S的中位数的k个数。

解决思路：

1、找出S的中位数median；

2、计算T={|x-median| | x属于S};

3、找出T中的第k小元素y；

4、根据y找出索要的解{x属于S | |x=median| <= y}； 

时间复杂度分析：

1、3需要时间O(n)。2、4需要O(n)时间，因此最坏时间为O(n)