l**h
发帖数: 893 | 1 老题了，还是不知道怎么找？
Find kth smallest element from an unsorted array in linear time. worst case
complexity should be O(n+k)
where n is array size. |
r**h
发帖数: 1288 | 2 先用partition找到前k大的k个元素，O(n)
再在前k大的里找最大的，O(k) |
p*****2
发帖数: 21240 | 3
worst case?
【在 r**h 的大作中提到】
: 先用partition找到前k大的k个元素，O(n)
: 再在前k大的里找最大的，O(k)
|
c*****a
发帖数: 808 | 4 quicksort partition 到k时，找左边最大，或者右边最小 |
m*****P
发帖数: 1331 | 5 CLRS里面找
大概就是利用quick sort的patition方法
一个是平均o(n)
要做到worst case o(n) 需要找特别的pivot 大概就是median的median
不过要写出来 估计面试不需要吧
【在 l**h 的大作中提到】
: 老题了，还是不知道怎么找？
: Find kth smallest element from an unsorted array in linear time. worst case
: complexity should be O(n+k)
: where n is array size.
|
j**7
发帖数: 143 | |
