编程之美之2.5 寻找最大的K个数

【题目】

有很多无序的数，从中找出最大的K个数。假定他们都不相等。

【解法一】

如果数据不是很多，例如在几千个左右，我们可以排一下序，从中找出最大的K个数。排序可以选择快速排序或者堆排序

[cpp] view
plaincopy

1. #include<stdio.h>  
2. #include<stdlib.h>  
3. int cmp(const void *a,const void *b){  
4.     return *(int *)a - *(int *)b;  
5. }  
6. int main(){  
7.     int n,k;  
8.     int Num[1000];  
9.     while(scanf("%d %d",&n,&k) != EOF){  
10.         //输入数据  
11.         for(int i = 0;i < n;i++){  
12.             scanf("%d",&Num[i]);  
13.         }  
14.         //排序  
15.         qsort(Num,n,sizeof(Num[0]),cmp);  
16.         //选出最大的K个数  
17.         for(i = n-k;i < n;i++){  
18.             printf("%d ",Num[i]);  
19.         }  
20.         printf("\n");  
21.     }  
22.     return 0;  
23. }  

【解法二】

我们可以继续对上面的算法进行优化，我们只是从这些无序的数中选出最大的K个数，并不需要前K个数据有序，也不需要后N-K个数据有序。

怎样才能避免做后N-K个数据有序呢？

回忆一下快速排序，快排中的每一步，都是将待排数据分做两组，其中一组的数据的任何一个数都比另一组中的任何一个大，然后再对两组分别做类似的操
作，然后继续下去……在本问题中，假设 N 个数存储在数组 S 中，我们从数组 S 中随机找出一个元素 X，把数组分为两部分 Sa 和 Sb。

Sa 中的元素大于等于 X，Sb 中元素小于 X。这时，有两种可能性：
1.   Sa中元素的个数小于K，Sa中所有的数和Sb中最大的K-|Sa|个元素（|Sa|指Sa中元素的个数）就是数组S中最大的K个数。
2.   Sa中元素的个数大于或等于K，则需要返回Sa中最大的K个元素。

这样递归下去，不断把问题分解成更小的问题，平均时间复杂度 O（N *log2K）。

[cpp] view
plaincopy

1. #include<stdio.h>  
2. #include<stdlib.h>  
3. //进行一次快速排序用哨兵数分割数组中的数据  
4. int Partition(int a[],int low,int high){  
5.     int i,j,index;  
6.     i = low;  
7.     j = high;  
8.     //哨兵  
9.     index = a[i];  
10.     while(i < j){  
11.         //从右向左找大于index的数来填a[i]  
12.         while(a[j] < index && i < j){  
13.             j--;  
14.         }  
15.         //把找到大于index的数赋值给a[i]  
16.         if(i < j){  
17.             a[i] = a[j];  
18.             i++;  
19.         }  
20.         //从左向右找小于index的数来填a[j]  
21.         while(a[i] >= index && i < j){  
22.             i++;  
23.         }  
24.         //把找到小于index的数赋值给a[j]  
25.         if(i < j){  
26.             a[j] = a[i];  
27.             j--;  
28.         }  
29.     }  
30.     a[i] = index;  
31.     return i;  
32. }  
33. int KBig(int a[],int low,int high,int k){  
34.     int index,n;  
35.     if(low < high){  
36.         //对数组进行划分，返回划分的位置  
37.         index = Partition(a,low,high);  
38.         n = index - low + 1;  
39.         //如果等于K返回第K个下标  
40.         if(n == k){  
41.             return index;  
42.         }  
43.         //不够K个再找k-n个  
44.         else if(n < k){  
45.             return KBig(a,index+1,high,k-n);  
46.         }  
47.         //如果大于K个则从些中选出最大的K个  
48.         else{  
49.             return KBig(a,low,index,k);  
50.         }  
51.     }  
52. }  
53.   
54. int main(){  
55.     int a[] = {4,5,1,6,2,7,3,8};  
56.     for(i = 0;i <= KBig(a,0,7,6);i++){  
57.         printf("%d ",a[i]);  
58.     }  
59.     printf("\n");  
60.     return 0;  
61. }  

【解法三】

用容量为K的最小堆来存储最大的K个数。最小堆的堆顶元素就是最大K个数中的最小的一个。每次扫描一个数据X，如果X比堆顶元素Y小，则不需要改变原来的堆，因为这个元素比最大的K个数要小。如果X比堆顶元素大，那么用X替换堆顶元素Y，在替换之后，X可能破坏了最小堆的结构，需要调整堆来维持堆的性质。调整过程时间复杂度为O(logK)。

当数据量很大时（100亿？这时候数据已经不能全部装入内存，所以要求尽可能少的遍历数组）可以采用这种方法。

[cpp] view
plaincopy

1. #include<stdio.h>  
2. #include<stdlib.h>  
3.   
4. //调整以index为根的子树  
5. //k：堆中元素个数  
6. int MinHeap(int a[],int index,int k){  
7.     int MinIndex = index;  
8.     //左子节点  
9.     int LeftIndex = 2*index;  
10.     //右子节点  
11.     int RightIndex = 2*index+1;  
12.     if(LeftIndex <= k && a[LeftIndex] < a[MinIndex]){  
13.         MinIndex = LeftIndex;  
14.     }  
15.     if(RightIndex <= k && a[RightIndex] < a[MinIndex]){  
16.         MinIndex = RightIndex;  
17.     }  
18.     //如果a[index]是最小的，则以index为根的子树已是最小堆否则index的子节点有最小元素  
19.     //则交换a[index],a[MinIndex],从而使index及子女满足堆性质  
20.     int temp;  
21.     if(MinIndex != index){  
22.         //交换a[index],a[MinIndex]  
23.         temp = a[index];  
24.         a[index] = a[MinIndex];  
25.         a[MinIndex] = temp;  
26.         //重新调整以MinIndex为根的子树  
27.         MinHeap(a,MinIndex,k);  
28.     }  
29.     return 0;  
30. }  
31.   
32.   
33. //建堆：将一个数组a[1-k]变成一个最小堆  
34. int BuildMinHeap(int a[],int k){  
35.     int i;  
36.     //用容量为k的最小堆来存储最大的k个数  
37.     for(i = k;i >= 1;i--){  
38.         //调整以i为根节点的树使之成为最小堆  
39.         MinHeap(a,i,k);  
40.     }  
41.     return 0;  
42. }  
43.   
44. int main(){  
45.     int n = 6;  
46.     int k = 3;  
47.     //a[0]不用，堆的根结点是从1开始的  
48.     int a[] = {0,3,17,8,27,7,20};  
49.     //BulidMaxHeap将输入数组构造一个最小堆  
50.     BuildMinHeap(a,k);  
51.     //数组中最小元素在根a[1]  
52.     for(int i = n;i > k;i--){  
53.         //如果X比堆顶元素Y小，则不需要改变原来的堆  
54.         //如果X比堆顶元素Y大，那么用X替换堆顶元素Y，在替换之后，X可能破坏了最小堆的结构，需要调整堆来维持堆的性质  
55.         int temp;  
56.         if(a[1] < a[i]){  
57.             //交换  
58.             temp = a[i];  
59.             a[i] = a[1];  
60.             a[1] = temp;  
61.             //重新调整，保持最小堆的性质  
62.             MinHeap(a,1,k);  
63.         }  
64.     }  
65.     for(i = 1;i <= k;i++){  
66.         printf("%d ",a[i]);  
67.     }  
68.     return 0;  
69. }  

如果不明白堆的用法，可以参考：堆排序

堆排序中主要讲解最大堆，最大堆和最小堆几乎一样。自己看看就知道了。

【解法四】

这个方法受到一定的限制。

如果所有N个数都是正整数，而且取值范围都不太大。可以考虑申请空间，记录每个整数出现的次数，然后再从大到小取最大的K个。

[cpp] view
plaincopy

1. #include<stdio.h>  
2. #include<string.h>  
3.   
4. const int MaxN = 100;  
5. int count[MaxN];  
6.   
7. int main(){  
8.     int k = 3;  
9.     int a[] = {3,17,8,27,7,20};  
10.     memset(count,0,MaxN);  
11.     //统计每个数重复次数  
12.     for(int i = 0;i < 6;i++){  
13.         count[a[i]]++;  
14.     }  
15.     //选取最大K个数  
16.     int sumCount = 0;  
17.     for(i = MaxN;i >= 0;i--){  
18.         sumCount += count[i];  
19.         if(sumCount >= k){  
20.             break;  
21.         }  
22.     }  
23.     //输出  
24.     int index = i;  
25.     for(i = index;i < MaxN;i++){  
26.         if(count[i] > 0){  
27.             printf("%d ",i);  
28.         }  
29.     }  
30.     printf("\n");  
31.     return 0;  
32. }