閱讀928 返回首頁    go 技術社區[雲棲]

編程之美之2.5 尋找最大的K個數

【題目】

有很多無序的數，從中找出最大的K個數。假定他們都不相等。

【解法一】

如果數據不是很多，例如在幾千個左右，我們可以排一下序，從中找出最大的K個數。排序可以選擇快速排序或者堆排序

  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）。

  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億？這時候數據已經不能全部裝入內存，所以要求盡可能少的遍曆數組）可以采用這種方法。

  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個。

  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. }  

最後更新：2017-04-03 08:26:12

  上一篇：go ObjectArx學習筆記-畫線
  下一篇：go 教你解決Sublime Text中文亂碼問題