首页 > 代码库 > 编程之美之2.5 寻找最大的K个数

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

2024-07-05 09:50:44   234人阅读

【题目】

有很多无序的数，从中找出最大的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. }  


联系
我们