`
SunnyYoona
  • 浏览: 361426 次
社区版块
存档分类
最新评论

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

 
阅读更多

【题目】

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

【解法一】

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

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. intcmp(constvoid*a,constvoid*b){
  4. return*(int*)a-*(int*)b;
  5. }
  6. intmain(){
  7. intn,k;
  8. intNum[1000];
  9. while(scanf("%d%d",&n,&k)!=EOF){
  10. //输入数据
  11. for(inti=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. return0;
  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)。

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. //进行一次快速排序用哨兵数分割数组中的数据
  4. intPartition(inta[],intlow,inthigh){
  5. inti,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. returni;
  32. }
  33. intKBig(inta[],intlow,inthigh,intk){
  34. intindex,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. returnindex;
  42. }
  43. //不够K个再找k-n个
  44. elseif(n<k){
  45. returnKBig(a,index+1,high,k-n);
  46. }
  47. //如果大于K个则从些中选出最大的K个
  48. else{
  49. returnKBig(a,low,index,k);
  50. }
  51. }
  52. }
  53. intmain(){
  54. inta[]={4,5,1,6,2,7,3,8};
  55. for(i=0;i<=KBig(a,0,7,6);i++){
  56. printf("%d",a[i]);
  57. }
  58. printf("\n");
  59. return0;
  60. }

【解法三】

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

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

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

如果不明白堆的用法,可以参考:堆排序

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

【解法四】

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

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

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

相关推荐

Global site tag (gtag.js) - Google Analytics