s********e
发帖数: 83 | 1 Find the first k smallest numbers in an array.
是不是先找到K+1大的值，然后遍历整个array，凡是<这个值，就加到结果里面 |
h******3
发帖数: 351 | 2 I think the idea is correct.
Also, think about special cases such as the array length is less than K. |
b******v
发帖数: 1493 | 3 就是用qsort的思想，找到第k小的元素，并partition
时间复杂度平均是O(n)
【在 s********e 的大作中提到】
: Find the first k smallest numbers in an array.
: 是不是先找到K+1大的值，然后遍历整个array，凡是<这个值，就加到结果里面
|
r****o
发帖数: 1950 | 4 I think so.
The book <> said this method has time complexity O(N
log2K).
It seems incorrect and should be O(N).
【在 b******v 的大作中提到】
: 就是用qsort的思想，找到第k小的元素，并partition
: 时间复杂度平均是O(n)
|
r*****l
发帖数: 216 | 5 也可以建一个有k个元素的最大堆，每次检查堆里最大的那个根元素和当前元素的大小
，总是keep当前最小的k个
时间复杂度也是O(N)
空间多了一个k-heap |
r****c
发帖数: 2585 | 6
this is N logk
In order to find in O(N), you need to find the kth number in O(N) which is a
simple extension of finding median in O(N)
【在 r*****l 的大作中提到】
: 也可以建一个有k个元素的最大堆，每次检查堆里最大的那个根元素和当前元素的大小
: ，总是keep当前最小的k个
: 时间复杂度也是O(N)
: 空间多了一个k-heap
|
f*********5
发帖数: 576 | 7 when u consider k as a constant,they just assume that this is O(N)
is a
【在 r****c 的大作中提到】
:
: this is N logk
: In order to find in O(N), you need to find the kth number in O(N) which is a
: simple extension of finding median in O(N)
|
g*****a
发帖数: 1457 | 8 use max heap or looser tree.
both big O are N*lg(k) |
