c**m
发帖数: 30 | 1 可能出现过N遍了，没看过的凑凑热闹：
Given N integers, find the first K largest. | w****i
发帖数: 964 | 2 function k_largest(array, k){
arrayk=sorted(array[1:k])
for x in array[k+1:end]{
if x>arrayk[end]: insert(arrayk, x) //~O(log(k))
}
}
not the best way
~O((k+n)log(k)), good for small k | w***g
发帖数: 5958 | 3 用heap保存topk, 复杂度O(NlogK)
【在 c**m 的大作中提到】
: 可能出现过N遍了，没看过的凑凑热闹：
: Given N integers, find the first K largest.
| w****i
发帖数: 964 | 4 刚才G了一下
heap=build_heap(array) //O(N)
for i=1:k{
largestk[i]=root(heap)
delete_root(heap) //O(log(N))
}
O(N+Klog(N)) |
|
