新手求解算法题

n个不同数的集合S,在O（n）时间内寻找离集合S的*值最近的k个数。
*值是从低到高排序的数列的第【n/2】位数。
最近的数是代表和*值的差最小的k个数。
求大神解答

17 个解决方案

#1

O(n)找到(n+k)/2和(n-k)/2两个数，然后再扫一遍数组拿出来所有在这两个数中间的数就可以了

#2

本来的集合是没排序过的，在O(n)时间内很难达成寻找到这2个数

#3

就是不用mergesort,二分法，快排，以外的在O(n)以内时间的方法

#4

引用 2 楼 u011502197 的回复:

本来的集合是没排序过的，在O(n)时间内很难达成寻找到这2个数

线性nth_element。自己看算法导论。一点也不难。

#5

引用 2 楼 u011502197 的回复:

本来的集合是没排序过的，在O(n)时间内很难达成寻找到这2个数

按照快排的那种思路是可以的吧

#6

就是编程之美上边的求最大k个数的变种，用最小堆排序，不过达不到o（n）把？应该是o（nlgk）
不过*值能在o（n）找到么？谁给个算法？

#7

引用 6 楼 nice_cxf 的回复:

就是编程之美上边的求最大k个数的变种，用最小堆排序，不过达不到o（n）把？应该是o（nlgk）
不过*值能在o（n）找到么？谁给个算法？

算法导论上有，linear median，qsort的框架，期望线性好写。严格线性也有，不过常数比较大，STL的nth_element也只要求期望线性。

#8

转义过来其实就是： 寻找第K大的数。

http://www.cnblogs.com/zhjp11/archive/2010/02/26/1674227.html
介绍了很多种方法，其中包括了o(n)复杂度。

#9

那如何能在O(n)下不但找出*值，而且得出最近的k个数，k个数需要比较和*值相差的大小
例如找出2k个数后，然后怎么操作才能让总体时间在O(n)之内

#10

寻找第(n/2-k)到（n/2+k）位大数之后，应该如何处理？

#11

引用 10 楼 u011502197 的回复:

寻找第(n/2-k)到（n/2+k）位大数之后，应该如何处理？

再数组从头到尾扫一遍，把在这两个数中间的数抓出来不就完了

#12

这有2k个数，要比较和*数的差，然后找出比*数差小的k个数
这个操作时间就不能再O(N)以内了

#13

1. 找出第(n-k)/2大的数，记为a，耗时O(n)
2. 找出第(n+k)/2大的数，记为b，耗时O(n)
3. 扫描数组，把a<=x<=b的所有x抓出来，耗时O(n)

你以为怎么做的？

#14

先把集合分为 5个数为一个组合的 n/5个part，
把每个part，sort后寻找每个part的中位数
每个part的中位数的在sort，后再寻找中位数---比较8回
就寻找出假定的*值  O（n/5）
然后在把每个part分为，比假定中位数大的数，比假定中位数小的数---比较3回
寻找出第 (n/2-k),....(n/2-1),(n/2),(n/2+1),....(n/2+k)位大的数   O(3n/4)
然后得出每位数和n/2位的差值
选出差值最小的k位数
但是还是很难在O(n)时间内

#15

比如 
input 1,2,3,4,5
输出*值最近的2位数
output (3,4,5);(2,3,4);(1,2,3)三组数据

#16

比如 
input  13，1，3,8,12，20,19，2
输出*值最近的3个数
output  (3,8,12,13)

#17

引用 13 楼 FancyMouse 的回复:

1. 找出第(n-k)/2大的数，记为a，耗时O(n)
2. 找出第(n+k)/2大的数，记为b，耗时O(n)
3. 扫描数组，把a<=x<=b的所有x抓出来，耗时O(n)

你以为怎么做的？

楼主的意思应该不是找到中位数的前后k/2个，而是找到离中位数最近的k个数，这不一定是前面取k/2个以及后面取k/2个。

我觉得可以这么做：
1. 找出中位数、第n/2+k以及n/2-k大的数，O(n)
2. 取出所有在n/2-k到n/2+k的数，将它们与中位数做差再取绝对值，得到一个大约2K大小的数组，O(n)
3. 再对新产生的数组取第K大的数，O(n)
4. 将新产生数组中所有小于第k大数的数找到与原始数组的对应值，这些数就是离原始数组中位数最近的K个数。O(n)
在K比较小的情况下，也可以使用最大堆。