l*****a
发帖数: 14598 | 1 用堆的话，扫描一次，time complexity O(Nlog2k) space complexity O(K).
if use quick select to find the Kth number,
then scan the 2nd time ,comparing the number with the kth one..
time complexity O(N),space complexity O(log2K)
scan time is more than the algorithm using heap.
看起来这地方有说道。。。
Correct me if i am wrong |
d**e
发帖数: 6098 | 2 用heap是因为找1st - kth个元素吧
quick select仅仅是找第kth元素
【在 l*****a 的大作中提到】
: 用堆的话，扫描一次，time complexity O(Nlog2k) space complexity O(K).
: if use quick select to find the Kth number,
: then scan the 2nd time ,comparing the number with the kth one..
: time complexity O(N),space complexity O(log2K)
: scan time is more than the algorithm using heap.
: 看起来这地方有说道。。。
: Correct me if i am wrong
|
l*****a
发帖数: 14598 | 3 再用它扫第二次不就得到你要的了
【在 d**e 的大作中提到】
: 用heap是因为找1st - kth个元素吧
: quick select仅仅是找第kth元素
|
h***n
发帖数: 276 | 4 对，把选择的k-th smallest得数当作pivot再partiion就好了
不过要保证选k-th smallest number的worst case complexity为O(n)，要用CLRS chap
9的比较复杂的算法
【在 l*****a 的大作中提到】
: 再用它扫第二次不就得到你要的了
|
d**e
发帖数: 6098 | 5 对哦，想漏了，sorry
【在 l*****a 的大作中提到】
: 再用它扫第二次不就得到你要的了
|
