e****9
发帖数: 316 | 1 如果N很小，可以用最小堆求前N大。
如果M和N都很大，有什么好的解法吗？ |
e****9
发帖数: 316 | |
g***s
发帖数: 3811 | 3 1. find n-th element O(n)
2. scan the array to get all elements which are less than n-th element
O(n)
【在 e****9 的大作中提到】
: 如果N很小，可以用最小堆求前N大。
: 如果M和N都很大，有什么好的解法吗？
|
e****9
发帖数: 316 | 4 1. find n-th element O(n)
上面这个不对吧。
怎么能一遍就把n-th项目扫出来呢？
【在 g***s 的大作中提到】
: 1. find n-th element O(n)
: 2. scan the array to get all elements which are less than n-th element
: O(n)
|
w****x
发帖数: 2483 | |
g***s
发帖数: 3811 | 6 O(n) != 一遍
check median-of-medians algorithm
【在 e****9 的大作中提到】
: 1. find n-th element O(n)
: 上面这个不对吧。
: 怎么能一遍就把n-th项目扫出来呢？
|
h*****3
发帖数: 1391 | 7 我觉的很象selecting sort.
1) 随便拿个数，算比它大的有多少（X）。比他小的有多少（Y）。排2边。
2)IF(X
2) IF(X>N),REPEAT 1) FROM X ARRAY |
e****9
发帖数: 316 | |
g***s
发帖数: 3811 | 9 it is linear-time on average, but O(n^2) on worst case.
【在 h*****3 的大作中提到】
: 我觉的很象selecting sort.
: 1) 随便拿个数，算比它大的有多少（X）。比他小的有多少（Y）。排2边。
: 2)IF(X: 2) IF(X>N),REPEAT 1) FROM X ARRAY
|
s***y
发帖数: 203 | 10 正解！！！
【在 h*****3 的大作中提到】
: 我觉的很象selecting sort.
: 1) 随便拿个数，算比它大的有多少（X）。比他小的有多少（Y）。排2边。
: 2)IF(X: 2) IF(X>N),REPEAT 1) FROM X ARRAY
|
g***s
发帖数: 3811 | 11 这个不要误导啊。
这个可以是给面试官的第一个solution，一般面试官会让你分析复杂度。然后问你如何
优化worst case。然后你再说median of medians algorithm就应该可以了。
【在 s***y 的大作中提到】
: 正解！！！
|
