b*****y
发帖数: 547 | 1 一个没有排序的数组里，挑出第K大的数
这种题型，通常要先做sort，再找出那个数吧，
请问最优化做法是。。。？ |
l*******b
发帖数: 2586 | 2 selection rank O(n) time |
b*****y
发帖数: 547 | 3 selection sorting ?
【在 l*******b 的大作中提到】
: selection rank O(n) time
|
l*******b
发帖数: 2586 | 4 http://en.wikipedia.org/wiki/Selection_algorithm
quick sort
【在 b*****y 的大作中提到】
: selection sorting ?
|
b*****y
发帖数: 547 | 5 这是最快的效率吗？
有没有lg(n)的？
【在 l*******b 的大作中提到】
: selection rank O(n) time
|
f*****7
发帖数: 92 | 6 你应该问面试官：是一次查询还是多次查询？
如果一次，就用CLRS上快排衍伸出的selection algorithm。如果partition算法可以确
保对半分，或者从概率角度出发，那就是O(N)时间，没有更快的。
如果多次，就先用最好的排序算法，排序预处理，之后每次的查询都是O(1)，如果次数
足够多，可以compensate排序的代价。
总之，第一个是学院派，第二个的工程的思维
你要让对方知道”做事情的方法，比算法本身更重要“ |
d**********x
发帖数: 4083 | 7 即使是一次查询，也不一定要用selection。
用堆可能看起来稍微慢一点，但是当k不大时，它的空间要求是很小的。
【在 f*****7 的大作中提到】
: 你应该问面试官：是一次查询还是多次查询？
: 如果一次，就用CLRS上快排衍伸出的selection algorithm。如果partition算法可以确
: 保对半分，或者从概率角度出发，那就是O(N)时间，没有更快的。
: 如果多次，就先用最好的排序算法，排序预处理，之后每次的查询都是O(1)，如果次数
: 足够多，可以compensate排序的代价。
: 总之，第一个是学院派，第二个的工程的思维
: 你要让对方知道”做事情的方法，比算法本身更重要“
|
b*****y
发帖数: 547 | 8 假设数组长度够大，比如20万个数， 无序排列，找出可重复的第K大的数
哪种算法最优化？
谢谢 |
l*****a
发帖数: 14598 | 9 quick select
【在 b*****y 的大作中提到】
: 一个没有排序的数组里，挑出第K大的数
: 这种题型，通常要先做sort，再找出那个数吧，
: 请问最优化做法是。。。？
|
