编程之美之2.5 寻找最大的K个数-阿里云开发者社区

【题目】

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

【解法一】

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

[cpp]view plaincopy 
   
 #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）。

[cpp]view plaincopy 
   
 #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亿？这时候数据已经不能全部装入内存，所以要求尽可能少的遍历数组）可以采用这种方法。

[cpp]view plaincopy 
   
 #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个。

[cpp]view plaincopy 
   
 #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;   
 }   

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

【题目】

【解法一】

【解法二】

【解法三】

【解法四】

热门文章

最新文章

相关电子书