l**h
发帖数: 893 | |
j*****y
发帖数: 1071 | 2 selection sort
【在 l**h 的大作中提到】
: 从一堆没有排序的整数中找出最大的K个.
|
p*****p
发帖数: 379 | 3 这是O(nk)的
【在 j*****y 的大作中提到】
: selection sort
|
j*****y
发帖数: 1071 | 4 select the (n-k)th element in the array, which is linear
【在 p*****p 的大作中提到】
: 这是O(nk)的
|
m*****1
发帖数: 147 | 5 这样行不行，开一个数组，长度为k，每次把这堆数扫一遍，取出最大的，放到数组中
，然后置为负，然后又继续扫，又取出当前最大的，直到找到了k个，这样复杂度是O（
KN)，从数量级上还是O（n）。。。。 |
s****0
发帖数: 117 | 6 no way
if it is doable, the worst case of qicksort will be O(nlogn).
【在 l**h 的大作中提到】
: 从一堆没有排序的整数中找出最大的K个.
|
p*****p
发帖数: 379 | 7 The array is not sorted so not possible to get that in linear time
qsort can do that in amortized O(n) but not worst case
【在 j*****y 的大作中提到】
: select the (n-k)th element in the array, which is linear
|
j*****y
发帖数: 1071 | 8 It can. just google "selection sort" :)
【在 p*****p 的大作中提到】
: The array is not sorted so not possible to get that in linear time
: qsort can do that in amortized O(n) but not worst case
|
r*******n
发帖数: 3020 | 9 可以，
result = []
1 left, right = partition // the elements in right > that of left
2 if sizeof(right) > k
drop the left, recursively call on the right.
else if sizeof(right) < k
k = k - sizeof(right)
append the right to the result.
recursively call on the left.
else
append the right to the result.
the end.
【在 s****0 的大作中提到】
: no way
: if it is doable, the worst case of qicksort will be O(nlogn).
|
p*****p
发帖数: 379 | 10 that takes n + n - 1 + ... + n - k - 1 which is O(nk)
【在 j*****y 的大作中提到】
: It can. just google "selection sort" :)
|
|
|
l*******b
发帖数: 2586 | |
S******t
发帖数: 151 | 12 First select the $K+1$-th element using the selection algorithm. This is $O(
n)$. And then use that element to partition. That's $O(n)$ as well. |
j*****y
发帖数: 1071 | 13 不是这么做的。
先找到第 n-k大的数 r，这个时间代价是 linear，
这个 是 call selection_sort(n, n-k)
然后扫描整个数组，比 r大的就留下, 这样就得到 k个最大的数了
【在 p*****p 的大作中提到】
: that takes n + n - 1 + ... + n - k - 1 which is O(nk)
|
p*****2
发帖数: 21240 | |
s****0
发帖数: 117 | 15 真丢人。把median of medians给忘了。
【在 s****0 的大作中提到】
: no way
: if it is doable, the worst case of qicksort will be O(nlogn).
|
d**********x
发帖数: 4083 | 16 median of medians并不实用，常数过大无比缓慢，只是作为一种理论上的kth element
可被worst-case O(n)找到的实例。
quick selection的worst case是O(n^2)，但是ramdomized之后效果很好，唯一问题是
它不是online算法，而且还要改原数组
所以在特定情形下heap也很好用，如果k相对于n是个很小的数
【在 s****0 的大作中提到】
: 真丢人。把median of medians给忘了。
|
b****g
发帖数: 192 | 17 Top k的问题是不是一般两种解法？
1.用heap sort的思路建一个大小为k的min heap
2.用selection rank，思路就类似quick sort
请问对吗？
【在 p*****2 的大作中提到】
: 这题还用讨论吗？上边好几个都说了。
|
l**h
发帖数: 893 | 18 according to wiki, selection sort is o(n^2).
If you only sort k element, it's still o(n*k), why you think its linear?
【在 j*****y 的大作中提到】
: It can. just google "selection sort" :)
|
S******t
发帖数: 151 | 19 $k$ is a constant.
【在 l**h 的大作中提到】
: according to wiki, selection sort is o(n^2).
: If you only sort k element, it's still o(n*k), why you think its linear?
|
d**********x
发帖数: 4083 | 20 说中文吧。。。
他其实是想说quick selection，而不是selection sort
【在 l**h 的大作中提到】
: according to wiki, selection sort is o(n^2).
: If you only sort k element, it's still o(n*k), why you think its linear?
|
|
|
d**********x
发帖数: 4083 | |
w********p
发帖数: 948 | 22 没有大的区别，很传统的题啊。
但是做题前，总是要清楚题，才好把清晰完整的思路给出来。
【在 d**********x 的大作中提到】
: 有区别么。。
:
: 数
|
d**********x
发帖数: 4083 | 23 思路也是一样的。。。
【在 w********p 的大作中提到】
: 没有大的区别，很传统的题啊。
: 但是做题前，总是要清楚题，才好把清晰完整的思路给出来。
|
A****e
发帖数: 310 | 24 我认为是这样的
【在 b****g 的大作中提到】
: Top k的问题是不是一般两种解法？
: 1.用heap sort的思路建一个大小为k的min heap
: 2.用selection rank，思路就类似quick sort
: 请问对吗？
|
r****o
发帖数: 1950 | 25 我觉得一般面试就用selection sort的办法，复杂度O(nk)，
当然这题可以用类似quick sort的方法，但是现场写出bug-free的代码基本上很难吧。
【在 l**h 的大作中提到】
: 从一堆没有排序的整数中找出最大的K个.
|
w********p
发帖数: 948 | 26 我个人认为我在解题前需要完全了解题目的意思。
就这样。
【在 d**********x 的大作中提到】
: 思路也是一样的。。。
|
w********p
发帖数: 948 | 27 我小小声的认为，这题一定要练习到用类似quick sort的二分法，然后bug-free的写出
来。
这题是基本题。比quicksort 简单。
【在 r****o 的大作中提到】
: 我觉得一般面试就用selection sort的办法，复杂度O(nk)，
: 当然这题可以用类似quick sort的方法，但是现场写出bug-free的代码基本上很难吧。
|
d**********x
发帖数: 4083 | 28 难度基本一样
就一个partition可能会写错
吧。
【在 w********p 的大作中提到】
: 我小小声的认为，这题一定要练习到用类似quick sort的二分法，然后bug-free的写出
: 来。
: 这题是基本题。比quicksort 简单。
|
h********3
发帖数: 2075 | 29 《算法导论》第九章。
【在 l**h 的大作中提到】
: 从一堆没有排序的整数中找出最大的K个.
|
l***z
发帖数: 9 | 30 可以用一个大小为k的heap，每次遇到大数插入heap，然后removeMin。
这样最后heap中是最大的k个数，O(nlogk) |
|
|
e***s
发帖数: 799 | |
