新鲜出炉的腾讯后台开发三面面试题！

cjaizss

6)100亿个数，求最大的1万个数，并说出算法的时间复杂度。

先找出第10000大的数k(时间复杂度O(n))，然后 ...
千年沉寂 发表于 2010-03-23 09:28

   高！！！

ztz0223

6)100亿个数，求最大的1万个数，并说出算法的时间复杂度。

先找出第10000大的数k(时间复杂度O(n))，然后 ...
千年沉寂 发表于 2010-03-23 09:28

   很不解
你这个算法，能达到o（n）？
找出第10000大的数，不是找出第二大第三大的数吧。而且我觉得你的算法可能要开一个1w的数组，每次插入都要排一下，如果你之前已经排序，那么可以二分，之后的每次插入也是一个o（logn）
而且之后的每一次插入难道都是o（1）？
你的算法我估计就是o（n×n）和o（logn×n）之间。

我觉得最好堆序，o（logn×n），稳定

ztz0223

[quote]6)100亿个数，求最大的1万个数，并说出算法的时间复杂度。

先找出第10000大的数k(时间复杂度O(n))，然后 ...
[size=2][color=#999999]千年沉寂

cjaizss

很不解
你这个算法，能达到o（n）？
找出第10000大的数，不是找出第二大第三大的数吧。而且我觉 ...
ztz0223 发表于 2010-03-23 22:00

    的确存在一个平均时间复杂度O(n)的算法,找到n长数组中第k大的数,参考快速排序中的每次调整.

luren04

学习

benjiam

高！！！
cjaizss 发表于 2010-03-23 19:59

    怎么找第1000 个大的k? 1000一个数字里面 怎么知道它是第1000个大？

okocha-jay

怎么找第1000 个大的k? 1000一个数字里面 怎么知道它是第1000个大？
benjiam 发表于 2010-03-24 09:25

    编程珠玑上介绍了一种quickselect,求第1000个大的数，那么最终数组的前1000个就是最小的那1000个；
书上是递归实现，最好转为非递归；
据上面介绍，KNUTH证明这种方法是线性的，3.4n

zgunix

   顶下  有意思！！


I chose to WOW Entertainment games, entertainment, Dailian wow game, to sell
Cheap wow gold If you need please contact me

petercheng750

太牛了

windfaddy

4）volitale的含义吧？
rain_fish 发表于 2010-03-18 09:32

    volatile...