算法技术手册 – 排序 – 求第K大的数

借助刚才的划分算法,我们可以比较容易的求出第K大的数,平均性能为O(N),最坏可能是O(N^2)。

注意关于idx的选择,随机的话效果会比选left、right和median好,如果数据不是很特殊的化。

拓展:
HDOJ
Kth number

Leave a Reply

Your email address will not be published.