Microsoft(2) 找出第k大的数

一个包含n个整数的一维数组，找出第k大的数(k<=n)

给出思路，时间空间复杂度。
有时间的实现你的算法，争取一次通过。

QuickSort, then pick the (k-1)-th element (assume k starts from 1 to n)
Average case:
Time Complexity = O(n log n) + O(1) = O(n log n)
Space Complexity = O(log n)
代码暂时没写

QuickSort, then pick the (k-1)-th element (assume k starts from 1 to n)
Average case:
Time Comple ...
argumentt 发表于 2011-4-19 13:12

    Can't disagree more

QuickSort, then pick the (k-1)-th element (assume k starts from 1 to n)
Average case:
Time Comple ...
argumentt 发表于 2011-4-19 13:12

If you use quicksort-like method, the time costs is O(n)
T(n) = T(n/2) + O(n)
You can prove it using Master Theorem, or just take an example...

Why does memory cost equal O(log n) ?
If you keep the original array, you got O(n)
if you use O(n log k) method, you got O(k) as memory cost...

If you use quicksort-like method, the time costs is O(n)
T(n) = T(n/2) + O(n)
You can prove it ...
vvnesaa 发表于 2011-4-19 19:33

   
MM 太聪明了。。。

回复 4# vvnesaa
这个问题在算法导论上有讨论，就是那个RANDOMIZED-SELECT问题吧，期望时间为Theta(n)的


   

以前写过，错了。这次又错了，改了几次才对

1. 
   
2. #include <vector>
   
3. #include <assert.h>
   
4. #include <random>
   
5. #include <time.h>
   
6. using namespace std;
   
7. 
   
8. int random(int p, int q)
   
9. {
   
10.      assert(p <= q);
    
11.      return rand() % (q - p + 1) + p;
    
12. }
    
13. 
    
14. void swap(int & a, int &b)
    
15. {
    
16.      int temp = a;
    
17.      a = b;
    
18.      b = temp;
    
19. }
    
20. 
    
21. int select(vector<int> &a, int p, int q)
    
22. {
    
23.      assert(p < q);
    
24.      swap(a[p], a[random(p, q - 1)]);
    
25.      int i = p;
    
26.      int x = a[p];
    
27.      int j = p + 1;
    
28.      while(true)
    
29.      {
    
30.       assert(j >= i);
    
31.       //find the nearest elements bigger than x
    
32.       while(j < q && a[j] > x) j++;
    
33.       if(j == q)
    
34.            break;
    
35.       i++;
    
36.       swap(a[j], a[i]);
    
37.       j++;
    
38.      }
    
39.      swap(a[i],a[p]);
    
40.      return(i);
    
41. }
    
42. 
    
43. int get_rank(vector<int> &a,int p, int q, int k)
    
44. {
    
45.      assert(p < q);
    
46.      //i = the index of the element that patition
    
47.      //the a[p..q] into 2 parts
    
48.      int i = select(a, p, q);
    
49.      //the rank of i in a[p..q]
    
50.      int j = i - p + 1;
    
51.      if (j == k)
    
52.       return a[i];
    
53.      if (j < k)
    
54.       return get_rank(a, i + 1, q, k - j);
    
55.      if (j > k)
    
56.       return get_rank(a, p, i, k);
    
57. }
    

复制代码

默默学习了……没怎么学CS果然很弱TAT
6L提到的Randomized-select我查了一下没看太懂……但感觉很妙
我还发现一个中文的paper，提到一种特殊的randomized-select方法，对于正整数数组可以把时间复杂度降到O(log n)，不知是否可行？
另外我想问，如果需要找很多个不同的第××大的数，random-select还是最有效的么？

类似快速排序的划分过程，o(n)