Microsoft(2) 找出第k大的数

回复 8# argumentt
其实这些东西也就当个现成结论用用，那个期望为什么是Theta(n)的证明估计就很少有人认真看。你说的东西都是这个问题的一些更深入研究了，估计很难一下想清楚。如果你研究算法，这些问题可能都是能发出paper的。

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

...
darksteel 发表于 2011-4-19 22:05

就是把快排的一次iteration从头开始的那个改成random就是了，还是快排的思想，没多大变化

回复 13# wwwyhx
有点那个意思，都是随机找个pivot，只不过快排要递归两边这个只要处理一边，复杂度就降下来了


   

wiki上有一个页面专门讲这个selection problem的en.wikipedia.org/wiki/Selection_algorithm

其中有一个Median of median 的方法，保证最差情况也是O(n)的
话说开发这方法的第一作者就图灵奖- -||

有个median of media，最差O(n)

1. #include <iostream>
   
2. 
   
3. using namespace std;
   
4. 
   
5. int select(int array[], int left, int right, int k) {
   
6.     int len = right - left;
   
7.     if (len <= 10) {
   
8.         for (int i = left + 1; i < right; ++i) {
   
9.             for (int j = i; j > left; --j) {
   
10.                 if (array[j] < array[j - 1]) {
    
11.                     array[j - 1] = array[j - 1]^array[j];
    
12.                     array[j] = array[j - 1]^array[j];
    
13.                     array[j - 1] = array[j - 1]^array[j];
    
14.                 }
    
15.             }
    
16.         }
    
17.         return left + k - 1;
    
18.     }
    
19.     int group_nums = len / 5;
    
20.     int x[group_nums];
    
21.     for (int i = 0; i < group_nums; ++i) {
    
22.         x[i] = array[select(array, left + i * 5, left + (i + 1) * 5, 3)];
    
23.     }
    
24.     int median = select(x, 0, group_nums, len / 10);
    
25.     for (int i = left; i < right; ++i)
    
26.         if (x[median] == array[i]) {
    
27.             median = i;
    
28.             break;
    
29.         }
    
30.     array[left] = array[left]^array[median];
    
31.     array[median] = array[left]^array[median];
    
32.     array[left] = array[left]^array[median];
    
33.     int i = left + 1;
    
34.     int j = right - 1;
    
35.     while (i < j) {
    
36.         while (array[i] < array[left]) ++i;
    
37.         while (array[j] > array[left]) --j;
    
38.         if (j <= i) break;
    
39.         array[i] = array[i]^array[j];
    
40.         array[j] = array[i]^array[j];
    
41.         array[i] = array[i]^array[j];
    
42.     }
    
43.     array[left] = array[left]^array[j];
    
44.     array[j] = array[left]^array[j];
    
45.     array[left] = array[left]^array[j];
    
46.     int t = j - left + 1;
    
47.     if (k == t) return j;
    
48.     if (k < t)
    
49.         return select(array, left, j , k);
    
50.     else
    
51.         return select(array, j + 1, right, k - t);
    
52. }
    
53. 
    
54. int main() {
    
55.     int n = 20;
    
56.     //cout << "input array size n" << endl;
    
57.     //cin >> n;
    
58.     int array[n];
    
59.     //cout << "input array element:" << endl;
    
60.     for (int i = 0; i < n; ++i) {
    
61.         array[i] = n - i;
    
62.     }
    
63. 
    
64.     cout << array[select(array, 0, n, 11)] << endl;
    
65.     cout << "k\tvalue" << endl;
    
66.     for (int i = 1; i <= n; ++i) {
    
67.         cout << i << "\t" << array[select(array, 0, n, i)] << endl;
    
68.     }
    
69.     return 0;
    
70. }

复制代码

wwwyhx 发表于 2011-4-19 21:23
MM 太聪明了。。。

。。。。。。quicksort是O(nlog(n))啊。。。worst case是O(n*n)的。。。。

Partition O(n)