Question

从一个容量为n的无序整数数组中，依次选出前K大的数（k<n），最优的时间复杂度是？

A： o(n)+o(klogn)
B： o(nlogn)+o(klogn)
C：o(nlogn)+o(nlogk)
D：o(nlogn)+o(k)

Answer 1

应选A，用的是快速排速的思想，第一次划分o(n)，然后在下面有选择的快排，可达o(klogn)故选A

Answer 2

D吧，用快速排序，再选前k个

Answer 3

构造堆(log N)然后一个一个往出抽 K 个(K log N)。

Answer 4

构造堆(N)然后一个一个往出抽 K 个(K log N)。