r**u
发帖数: 1567 | 1 Given a set S of n distinct numbers and a positive integer k <= n. Determine
the k numbers in S that are closest to the median of S. Find an O(n)
algorithm.
这个就是先找到median，然后搞个max heap，每个数都有个到median的distance, 如果
小于heap顶，放到heap，O(nlogk)。对不？ |
g*******y
发帖数: 1930 | 2 达不到要求
题目说的是O(n)
而k是小于等于n的数
O(nlogk) = O(nlogn)
其实可以这样：
找到median后，对于每个数，算一个新的数组b[i] = abs(a[i]-median)
然后在b[i]中找k-th元素，然后再遍历一遍就可以找到k个最小的了。
这样保证是O(n)
这个题告诉我们，heap也不是万金油，呵呵 |
r**u
发帖数: 1567 | 3 got it. 还好这个不用又构造一颗树，向左走，向右走，呵呵。谢谢
【在 g*******y 的大作中提到】
: 达不到要求
: 题目说的是O(n)
: 而k是小于等于n的数
: O(nlogk) = O(nlogn)
: 其实可以这样：
: 找到median后，对于每个数，算一个新的数组b[i] = abs(a[i]-median)
: 然后在b[i]中找k-th元素，然后再遍历一遍就可以找到k个最小的了。
: 这样保证是O(n)
: 这个题告诉我们，heap也不是万金油，呵呵
|
a********a
发帖数: 219 | 4 你真是太强了。不敢想像你还在找工作。应该工作找你才是。
【在 g*******y 的大作中提到】
: 达不到要求
: 题目说的是O(n)
: 而k是小于等于n的数
: O(nlogk) = O(nlogn)
: 其实可以这样：
: 找到median后，对于每个数，算一个新的数组b[i] = abs(a[i]-median)
: 然后在b[i]中找k-th元素，然后再遍历一遍就可以找到k个最小的了。
: 这样保证是O(n)
: 这个题告诉我们，heap也不是万金油，呵呵
|
r****o
发帖数: 1950 | 5 在b[i]中找k-th元素怎么才能用O(n)时间找到呢?
【在 g*******y 的大作中提到】
: 达不到要求
: 题目说的是O(n)
: 而k是小于等于n的数
: O(nlogk) = O(nlogn)
: 其实可以这样：
: 找到median后，对于每个数，算一个新的数组b[i] = abs(a[i]-median)
: 然后在b[i]中找k-th元素，然后再遍历一遍就可以找到k个最小的了。
: 这样保证是O(n)
: 这个题告诉我们，heap也不是万金油，呵呵
|
c*********n
发帖数: 1057 | 6 CLRS selection那章就讲这个的吧，还严格证明了
【在 r****o 的大作中提到】
: 在b[i]中找k-th元素怎么才能用O(n)时间找到呢?
|
k***e
发帖数: 556 | 7 linear selection
check you algorithm textbook
【在 r****o 的大作中提到】
: 在b[i]中找k-th元素怎么才能用O(n)时间找到呢?
|
c*********n
发帖数: 1057 | 8 努re，这样的人还找不到工作我们好不要找了
【在 a********a 的大作中提到】
: 你真是太强了。不敢想像你还在找工作。应该工作找你才是。
|
r****o
发帖数: 1950 | 9 谢谢，我没看到有selection这章阿，
能否告诉具体的章节数?
【在 c*********n 的大作中提到】
: CLRS selection那章就讲这个的吧，还严格证明了
|
H*M
发帖数: 1268 | 10 its called order statistics
【在 r****o 的大作中提到】
: 谢谢，我没看到有selection这章阿，
: 能否告诉具体的章节数?
|
r****o
发帖数: 1950 | 11 多谢，以前学过的又忘光了。
【在 H*M 的大作中提到】
: its called order statistics
|
c*********n
发帖数: 1057 | 12 我也感觉，这种东西过段时间不看就忘了哎
【在 r****o 的大作中提到】
: 多谢，以前学过的又忘光了。
|
k***e
发帖数: 556 | 13 你天天上这来看 保你记得牢
【在 c*********n 的大作中提到】
: 我也感觉，这种东西过段时间不看就忘了哎
|
