问道算法题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问道算法题

问道算法题# JobHunting - 待字闺中

p*i2012-03-07 08:03

1 楼

题目是：
How to find the kth largest element in an unsorted array of length n in O(n)
?

s*n2012-03-07 08:03

2 楼

use a heap of size k

p*i2012-03-07 08:03

3 楼

大哥能不能具体点？

【在 s******n 的大作中提到】

: use a heap of size k

H*12012-03-07 08:03

4 楼

o(n ln k)
maintain a heap of size k

n)

【在 p*****i 的大作中提到】

: 题目是：
: How to find the kth largest element in an unsorted array of length n in O(n)
: ?

s*82012-03-07 08:03

5 楼

if k is fixed
ln k = constant

【在 H*****1 的大作中提到】

: o(n ln k)
: maintain a heap of size k
:
: n)

H*12012-03-07 08:03

6 楼

用前k个数做一个min heap
扫描剩下的数，如果比heap的根节点小就算了，如果大，就加到heap里，同时把heap的
根节点去掉
最后返回heap的根节点

【在 p*****i 的大作中提到】

: 大哥能不能具体点？

p*i2012-03-07 08:03

7 楼

谢谢帮忙，小弟懂了，哈哈

【在 H*****1 的大作中提到】

: 用前k个数做一个min heap
: 扫描剩下的数，如果比heap的根节点小就算了，如果大，就加到heap里，同时把heap的
: 根节点去掉
: 最后返回heap的根节点

y*n2012-03-07 08:03

8 楼

....heap得有lgk的插入吧。。。k也不是常量啊。k为n不就是lgln了么。

c*52012-03-07 08:03

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 的大作中提到】

: 谢谢帮忙，小弟懂了，哈哈

C*U2012-03-07 08:03

10 楼

算法导论里有详细算法
用recursion
对任何k都可以。

n)

【在 p*****i 的大作中提到】

: 题目是：
: How to find the kth largest element in an unsorted array of length n in O(n)
: ?

f*n2012-03-07 08:03

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 的大作中提到】

: 题目是：
: How to find the kth largest element in an unsorted array of length n in O(n)
: ?

w*z2012-03-07 08:03

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 的大作中提到】

: 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*r2012-03-07 08:03

13 楼

经典算法，搜一下就知道
ls说得很清楚
要让时间接近线性，可以多选几个pivot,然后取中值

w*o2012-03-07 08:03

14 楼

这个有点儿overkill,你得到的其实是最大的k个数，有点儿任务完成的太充裕了。
版主想要的是第k大的数，要求O(n)

【在 H*****1 的大作中提到】

: 用前k个数做一个min heap
: 扫描剩下的数，如果比heap的根节点小就算了，如果大，就加到heap里，同时把heap的
: 根节点去掉
: 最后返回heap的根节点

s*e2012-03-07 08:03

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 的大作中提到】

: 题目是：
: How to find the kth largest element in an unsorted array of length n in O(n)
: ?