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

千年沉寂

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

先找出第10000大的数k(时间复杂度O(n))，然后只要选择比k大的即可(时间复杂度O(n))，不足10000用k补充。（100亿太大，可以分段）
总的时间复杂度还是O(n)。

千年沉寂

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

可以的，平均时间达到O(n)

类似于二分法：
1.每次随机选取一个数 n，扫描一遍，使n 的左边都比 n小(l个元素)，右边都比 n 大(r 个元素)。
2.
    A:若满足条件，则返回n;
    B:若k>l,只对n右边的元素返回第一步执行;
    C:若k>r,只对n左边的元素返回第一步执行;

B,C每次只需执行一项，因此平均复杂度大概为：O(n+n/2+n/4...)=O(2n)=O(n)

千年沉寂

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

见113楼

千年沉寂

能讲详细点嘛，说实话，没太看明白。快速排序和折半排序都我都明白，但你这个真没看明白，希望能展开详 ...
dozec 发表于 2010-03-25 23:43

实际上是模仿快速排序算法设计的，其基本思想也是对输入数组进行划分。不同的是，它只对划分出的子数组之一进行处理。
过程大致如下：

1. int RandomSelect(int a[], int left, int right, int k)
   
2. {
   
3.         int i,j,p;
   
4.         if (right <= 1) return a[right];
   
5.         i = RandomPartition(a[], left, right);
   
6.         /************************************************
   
7.         * RandomPartition,把a[left:right]随机划分为:
   
8.         * a[left : i-1] <= a[i] <= a[i+1 : right].
   
9.         *************************************************/
   
10.         j = right - i + 1;
    
11.         /* j 为 a[i : right] 的元素个数*/
    
12.         if (j == k) return a[i];
    
13.         if (j > k)
    
14.             /* 第k大的数在右子数组 */
    
15.             return RandomSelect(a, i+1, right, k);
    
16.         else
    
17.             /* 第k大的数在左子数组 */
    
18.             return RandomSelect(a, left, i-1 , k-j);
    
19. }

复制代码