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 的大作中提到】
: use a heap of size k
|
H*****1
发帖数: 4815 | 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*******8
发帖数: 12734 | 5 if k is fixed
ln k = constant
【在 H*****1 的大作中提到】
: o(n ln k)
: maintain a heap of size k
:
: n)
|
H*****1
发帖数: 4815 | 6 用前k个数做一个min heap
扫描剩下的数，如果比heap的根节点小就算了，如果大，就加到heap里，同时把heap的
根节点去掉
最后返回heap的根节点
【在 p*****i 的大作中提到】
: 大哥 能不能具体点？
|
p*****i
发帖数: 197 | 7 谢谢帮忙，小弟懂了，哈哈
【在 H*****1 的大作中提到】
: 用前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 的大作中提到】
: 谢谢帮忙，小弟懂了，哈哈
|
C***U
发帖数: 2406 | 10 算法导论里有详细算法
用recursion
对任何k都可以。
n)
【在 p*****i 的大作中提到】
: 题目是：
: 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 的大作中提到】
: 题目是：
: 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 的大作中提到】
: 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 的大作中提到】
: 用前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 的大作中提到】
: 题目是：
: 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 的大作中提到】
: 题目是：
: 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 的大作中提到】
: 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 的大作中提到】
: 题目是：
: How to find the kth largest element in an unsorted array of length n in O(n)
: ?
|
