跟人聊了一道题，怎么做最优。 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

跟人聊了一道题，怎么做最优。

跟人聊了一道题，怎么做最优。# JobHunting - 待字闺中

y*62016-04-12 07:04

1 楼

就是一个大数组里面（unsorted) 要找sum of 最大的k 个数
int kSum (int [] array, int k);
不就是用heap (priorityQueue) keep the biggest k number 吗? 还能有什么更好的
方法吗？面试的好像说有，但不说怎么办。

S*t2016-04-12 07:04

2 楼

kth largest element can be found in O(n)
I think you can find it in algo textbook, or just google it

【在 y*******6 的大作中提到】

: 就是一个大数组里面（unsorted) 要找sum of 最大的k 个数
: int kSum (int [] array, int k);
: 不就是用heap (priorityQueue) keep the biggest k number 吗? 还能有什么更好的
: 方法吗？面试的好像说有，但不说怎么办。

V*a2016-04-12 07:04

3 楼

类似quick sort的算法，复杂度O(n)，好像叫quick select来着，能找到最大的k个数。

y*a2016-04-12 07:04

4 楼

median of medians.
The nth element of the array after you run the algorithm will be the nth
biggest element, and the right side will be of all bigger numbers bigger
than the nth.
The complexity of the algorithm is O(n).

【在 y*******6 的大作中提到】