S**Y
发帖数: 136 | 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) algori
thm
感觉不太可能
谁给讲讲? |
g*******y
发帖数: 1930 | 2 why not?
find the median -- O(n)
compute the absolute value b[i] = |a[i] - median| -- O(n)
find kth element of b[i] -- O(n)
scan through b[i] find all numbers greater than kth element -- O(n) |
S**Y
发帖数: 136 | 3 thanks.
for the first step, u mean the group-5 linear median method?
【在 g*******y 的大作中提到】
: why not?
: find the median -- O(n)
: compute the absolute value b[i] = |a[i] - median| -- O(n)
: find kth element of b[i] -- O(n)
: scan through b[i] find all numbers greater than kth element -- O(n)
|
m******9
发帖数: 968 | 4 我还没跟上你的思路，比如如下的这个例子，能不能就着例子解释一下呀，谢谢
比如： k = 2
a: 1, 2, 3, 4, 5, 6, 7
median就是4，
那么b就是：
b: 3, 2, 1, 0, 1, 2, 3
【在 g*******y 的大作中提到】
: why not?
: find the median -- O(n)
: compute the absolute value b[i] = |a[i] - median| -- O(n)
: find kth element of b[i] -- O(n)
: scan through b[i] find all numbers greater than kth element -- O(n)
|
r****o
发帖数: 1950 | 5 find Kth element of b[i] in O(n)
这一步好像挺麻烦啊。
【在 g*******y 的大作中提到】
: why not?
: find the median -- O(n)
: compute the absolute value b[i] = |a[i] - median| -- O(n)
: find kth element of b[i] -- O(n)
: scan through b[i] find all numbers greater than kth element -- O(n)
|
f*****e
发帖数: 2992 | 6 把CLRS的题目做的滚瓜烂熟,你问这个问题,说明order statistics那一章没有认真看.
这本书有两个答案,一个是一般的solution,另一个是instructor's manual,网上都可以
下到.他说的那个就是答案.
【在 r****o 的大作中提到】
: find Kth element of b[i] in O(n)
: 这一步好像挺麻烦啊。
|
m*****f
发帖数: 1243 | 7 其实很多面试题原题就在CLRS课后习题， 这题似乎就类似linear selection那章后面
的一道 |
r********g
发帖数: 1351 | 8 请问哪里可以下到课后题的答案吗？
【在 m*****f 的大作中提到】
: 其实很多面试题原题就在CLRS课后习题， 这题似乎就类似linear selection那章后面
: 的一道
|
m*****f
发帖数: 1243 | 9 网上找找吧, 有些不全的
【在 r********g 的大作中提到】
: 请问哪里可以下到课后题的答案吗？
|
r********g
发帖数: 1351 | 10 果真很容易找到。。。晕，以前上课的时候都不知道有这东西。。
http://blog.chinaunix.net/u/18517/showart_487811.html
【在 m*****f 的大作中提到】
: 网上找找吧, 有些不全的
|
j**0
发帖数: 11 | |
g*****u
发帖数: 298 | 12 这个需要O(n)空间
有没有要O（1）空间的？
【在 g*******y 的大作中提到】
: why not?
: find the median -- O(n)
: compute the absolute value b[i] = |a[i] - median| -- O(n)
: find kth element of b[i] -- O(n)
: scan through b[i] find all numbers greater than kth element -- O(n)
|
b****j
发帖数: 78 | 13 其实可以做到空间O(1)
每当你需要b[i]的时候，用a[i]直接计算一下
【在 g*****u 的大作中提到】
: 这个需要O(n)空间
: 有没有要O（1）空间的？
|
