p*****i 发帖数: 197 | 1 题目是:
How to find the kth largest element in an unsorted array of length n in O(n)
? |
s******n 发帖数: 3946 | |
p*****i 发帖数: 197 | 3 大哥 能不能具体点?
【在 s******n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : use a heap of size k
|
H*****1 发帖数: 4815 | 4 o(n ln k)
maintain a heap of size k
n)
【在 p*****i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 题目是: : How to find the kth largest element in an unsorted array of length n in O(n) : ?
|
s*******8 发帖数: 12734 | 5 if k is fixed
ln k = constant
【在 H*****1 的大作中提到】![](/moin_static193/solenoid/img/up.png) : o(n ln k) : maintain a heap of size k : : n)
|
H*****1 发帖数: 4815 | 6 用前k个数做一个min heap
扫描剩下的数,如果比heap的根节点小就算了,如果大,就加到heap里,同时把heap的
根节点去掉
最后返回heap的根节点
【在 p*****i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 大哥 能不能具体点?
|
p*****i 发帖数: 197 | 7 谢谢帮忙,小弟懂了,哈哈
【在 H*****1 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 用前k个数做一个min heap : 扫描剩下的数,如果比heap的根节点小就算了,如果大,就加到heap里,同时把heap的 : 根节点去掉 : 最后返回heap的根节点
|
y*****n 发帖数: 243 | 8 ....heap得有lgk的插入吧。。。k也不是常量啊。k为n不就是lgln了么。 |
c*****5 发帖数: 25 | 9 Isn't this order statistic problem? Recursive selection based on random-
partition will get the kth element in theta(n) time.
题目是:How to find the kth largest element in an unsorted array of length n
in O(n)?
★ Sent from iPhone App: iReader Mitbbs 7.39 - iPad Lite
【在 p*****i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 谢谢帮忙,小弟懂了,哈哈
|
C***U 发帖数: 2406 | 10 算法导论里有详细算法
用recursion
对任何k都可以。
n)
【在 p*****i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 题目是: : How to find the kth largest element in an unsorted array of length n in O(n) : ?
|
|
|
f*******n 发帖数: 12623 | 11 This is the famous linear-time selection algorithm. It is very
complicated. They won't expect you to tell exactly how it works; just that you know about it.
http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general
n)
【在 p*****i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 题目是: : How to find the kth largest element in an unsorted array of length n in O(n) : ?
|
w**z 发帖数: 8232 | 12 It's like the quick sort, pick the pivot. But to handle worst case for
picking the pivot , you need to have the "median of median" thing.
you know about it.
【在 f*******n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : This is the famous linear-time selection algorithm. It is very : complicated. They won't expect you to tell exactly how it works; just that you know about it. : http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general : : n)
|
i******r 发帖数: 793 | 13 经典算法,搜一下就知道
ls说得很清楚
要让时间接近线性,可以多选几个pivot,然后取中值 |
w****o 发帖数: 2260 | 14 这个有点儿overkill,你得到的其实是最大的k个数,有点儿任务完成的太充裕了。
版主想要的是第k大的数,要求O(n)
【在 H*****1 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 用前k个数做一个min heap : 扫描剩下的数,如果比heap的根节点小就算了,如果大,就加到heap里,同时把heap的 : 根节点去掉 : 最后返回heap的根节点
|
s****e 发帖数: 638 | 15 试试
int findKth(int* arr, int start, int end, int k, int last) {
if (start == end) return start;
int s1 = start;
int e1 = end;
int mid = arr[(e1+s1)/2];
while(s1 < e1) {
while(arr[s1] < mid) s1 ++;
while(arr[e1] > mid) e1 --;
if (s1 <= e1) {
int temp = arr[s1];
arr[s1] = arr[e1];
arr[e1] = temp;
s1++;
e1--;
}
}
if (last-s1 >= k) return findKth(arr, s1, end, k, last);
else return findKth(arr, start, s1-1, k, last);
}
n)
【在 p*****i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 题目是: : How to find the kth largest element in an unsorted array of length n in O(n) : ?
|
h**********d 发帖数: 4313 | 16 如果k不大的话,可以维护k个变量,然后线性扫描一遍数组,同时update这k个变量就
完了
n)
★ 发自iPhone App: ChineseWeb - 中文网站浏览器
【在 p*****i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 题目是: : How to find the kth largest element in an unsorted array of length n in O(n) : ?
|
l***i 发帖数: 1309 | 17 1. you can find median in O(n) time
2. if k
else throw away lower half
and you end up with n + n/2 + ... + 1 = O(n) |
w****o 发帖数: 2260 | 18 你正好说反了,他说的是kth largest, 你的解法是kth smallest
【在 l***i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 1. you can find median in O(n) time : 2. if k: else throw away lower half : and you end up with n + n/2 + ... + 1 = O(n)
|
m******6 发帖数: 82 | 19 partition/2?
n)
【在 p*****i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 题目是: : How to find the kth largest element in an unsorted array of length n in O(n) : ?
|