【题目】
有很多无序的数，从中找出最大的K个数。假定他们都不相等。
【解法一】
如果数据不是很多，例如在几千个左右，我们可以排一下序，从中找出最大的K个数。排序可以选择快速排序或者堆排序
- #include<stdio.h>
- #include<stdlib.h>
- int cmp(const void *a,const void *b){
- return *(int *)a - *(int *)b;
- }
- int main(){
- int n,k;
- int Num[1000];
- while(scanf("%d %d",&n,&k) != EOF){
- //输入数据
- for(int i = 0;i < n;i++){
- scanf("%d",&Num[i]);
- }
- //排序
- qsort(Num,n,sizeof(Num[0]),cmp);
- //选出最大的K个数
- for(i = n-k;i < n;i++){
- printf("%d ",Num[i]);
- }
- printf("\n");
- }
- return 0;
- }
【解法二】
我们可以继续对上面的算法进行优化，我们只是从这些无序的数中选出最大的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）。
- #include<stdio.h>
- #include<stdlib.h>
- //进行一次快速排序用哨兵数分割数组中的数据
- int Partition(int a[],int low,int high){
- int i,j,index;
- i = low;
- j = high;
- //哨兵
- index = a[i];
- while(i < j){
- //从右向左找大于index的数来填a[i]
- while(a[j] < index && i < j){
- j--;
- }
- //把找到大于index的数赋值给a[i]
- if(i < j){
- a[i] = a[j];
- i++;
- }
- //从左向右找小于index的数来填a[j]
- while(a[i] >= index && i < j){
- i++;
- }
- //把找到小于index的数赋值给a[j]
- if(i < j){
- a[j] = a[i];
- j--;
- }
- }
- a[i] = index;
- return i;
- }
- int KBig(int a[],int low,int high,int k){
- int index,n;
- if(low < high){
- //对数组进行划分，返回划分的位置
- index = Partition(a,low,high);
- n = index - low + 1;
- //如果等于K返回第K个下标
- if(n == k){
- return index;
- }
- //不够K个再找k-n个
- else if(n < k){
- return KBig(a,index+1,high,k-n);
- }
- //如果大于K个则从些中选出最大的K个
- else{
- return KBig(a,low,index,k);
- }
- }
- }
- int main(){
- int a[] = {4,5,1,6,2,7,3,8};
- for(i = 0;i <= KBig(a,0,7,6);i++){
- printf("%d ",a[i]);
- }
- printf("\n");
- return 0;
- }
【解法三】
用容量为K的最小堆来存储最大的K个数。最小堆的堆顶元素就是最大K个数中的最小的一个。每次扫描一个数据X，如果X比堆顶元素Y小，则不需要改变原来的堆，因为这个元素比最大的K个数要小。如果X比堆顶元素大，那么用X替换堆顶元素Y，在替换之后，X可能破坏了最小堆的结构，需要调整堆来维持堆的性质。调整过程时间复杂度为O(logK)。
当数据量很大时（100亿？这时候数据已经不能全部装入内存，所以要求尽可能少的遍历数组）可以采用这种方法。
- #include<stdio.h>
- #include<stdlib.h>
- //调整以index为根的子树
- //k：堆中元素个数
- int MinHeap(int a[],int index,int k){
- int MinIndex = index;
- //左子节点
- int LeftIndex = 2*index;
- //右子节点
- int RightIndex = 2*index+1;
- if(LeftIndex <= k && a[LeftIndex] < a[MinIndex]){
- MinIndex = LeftIndex;
- }
- if(RightIndex <= k && a[RightIndex] < a[MinIndex]){
- MinIndex = RightIndex;
- }
- //如果a[index]是最小的，则以index为根的子树已是最小堆否则index的子节点有最小元素
- //则交换a[index],a[MinIndex],从而使index及子女满足堆性质
- int temp;
- if(MinIndex != index){
- //交换a[index],a[MinIndex]
- temp = a[index];
- a[index] = a[MinIndex];
- a[MinIndex] = temp;
- //重新调整以MinIndex为根的子树
- MinHeap(a,MinIndex,k);
- }
- return 0;
- }
- //建堆：将一个数组a[1-k]变成一个最小堆
- int BuildMinHeap(int a[],int k){
- int i;
- //用容量为k的最小堆来存储最大的k个数
- for(i = k;i >= 1;i--){
- //调整以i为根节点的树使之成为最小堆
- MinHeap(a,i,k);
- }
- return 0;
- }
- int main(){
- int n = 6;
- int k = 3;
- //a[0]不用，堆的根结点是从1开始的
- int a[] = {0,3,17,8,27,7,20};
- //BulidMaxHeap将输入数组构造一个最小堆
- BuildMinHeap(a,k);
- //数组中最小元素在根a[1]
- for(int i = n;i > k;i--){
- //如果X比堆顶元素Y小，则不需要改变原来的堆
- //如果X比堆顶元素Y大，那么用X替换堆顶元素Y，在替换之后，X可能破坏了最小堆的结构，需要调整堆来维持堆的性质
- int temp;
- if(a[1] < a[i]){
- //交换
- temp = a[i];
- a[i] = a[1];
- a[1] = temp;
- //重新调整，保持最小堆的性质
- MinHeap(a,1,k);
- }
- }
- for(i = 1;i <= k;i++){
- printf("%d ",a[i]);
- }
- return 0;
- }
如果不明白堆的用法，可以参考：堆排序
堆排序中主要讲解最大堆，最大堆和最小堆几乎一样。自己看看就知道了。
【解法四】
这个方法受到一定的限制。
如果所有N个数都是正整数，而且取值范围都不太大。可以考虑申请空间，记录每个整数出现的次数，然后再从大到小取最大的K个。
- #include<stdio.h>
- #include<string.h>
- const int MaxN = 100;
- int count[MaxN];
- int main(){
- int k = 3;
- int a[] = {3,17,8,27,7,20};
- memset(count,0,MaxN);
- //统计每个数重复次数
- for(int i = 0;i < 6;i++){
- count[a[i]]++;
- }
- //选取最大K个数
- int sumCount = 0;
- for(i = MaxN;i >= 0;i--){
- sumCount += count[i];
- if(sumCount >= k){
- break;
- }
- }
- //输出
- int index = i;
- for(i = index;i < MaxN;i++){
- if(count[i] > 0){
- printf("%d ",i);
- }
- }
- printf("\n");
- return 0;
- }
