找出一堆数据中最大或者最小的K个数

时间:2020-12-21 00:43:44

转自找出一堆数据中最大或者最小的K个数

用容量为K的最小堆来存储最大的K个数,最小堆的堆顶元素就是最大K个数中最小的一个。每次考虑一个新的元素时,将其与堆顶的元素进行比较,只有当它大于堆顶元素时,才用其替换堆顶元素,并更新最小堆。时间复杂度为O(N*logK)。


找出最大的K个数方法是建立一个有K个数的最小堆。

[cpp]  view plain copy 找出一堆数据中最大或者最小的K个数 找出一堆数据中最大或者最小的K个数
  1. #include <iostream>  
  2. #include <vector>  
  3. #include <set>  
  4.   
  5. using namespace std;  
  6.   
  7. typedef multiset< int,less<int> >  INTHEAP;  
  8.   
  9. void FindGreatestNum(vector<int>& iArray, const unsigned int num, INTHEAP& pRes)  
  10. {  
  11.     pRes.clear();  
  12.     if(iArray.empty() || num <= 0)  
  13.     {  
  14.         return;  
  15.     }  
  16.   
  17.     vector<int>::iterator iter = iArray.begin();  
  18.     while(iter != iArray.end())  
  19.     {  
  20.         if(pRes.size() < num)  
  21.         {  
  22.             pRes.insert(*iter);  
  23.         }  
  24.         else  
  25.         {  
  26.             INTHEAP::iterator pIter = pRes.begin();  
  27.             if(*iter > *pIter)  
  28.             {  
  29.                 pRes.erase(pIter);  
  30.                 pRes.insert(*iter);   
  31.             }  
  32.         }  
  33.         iter ++;  
  34.     }  
  35. }  
  36. int main()  
  37. {  
  38.     int iArray[] = {1,6,9,0,2,8,12,77,90,54,78,92,23,34,56,76,91};  
  39.     int len =  sizeof( iArray ) / sizeofint );  
  40.     const unsigned int num = 7;  
  41.     vector<int> nArray(iArray, iArray + len);  
  42.   
  43.     INTHEAP pRes;  
  44.     FindGreatestNum(nArray, num, pRes);  
  45.     INTHEAP::iterator iter = pRes.begin();  
  46.     while(iter != pRes.end())  
  47.     {  
  48.         cout<<*iter<<" ";  
  49.         iter ++;  
  50.     }  
  51.     cout<<endl;  
  52.     return 0;  
  53. }  

同理:找出最小的K个数方法是建立一个有K个数的最大堆。

[cpp]  view plain copy 找出一堆数据中最大或者最小的K个数 找出一堆数据中最大或者最小的K个数
  1. #include <iostream>  
  2. #include <set>  
  3. #include <vector>  
  4.   
  5. using namespace std;  
  6. typedef multiset<int, greater < int > >  intHeap;  
  7.   
  8. void FindKLeastNumbers(vector< int >& iArray,const unsigned int num,intHeap& pResult)  
  9. {  
  10.     pResult.clear();  
  11.     if(iArray.empty() || num <= 0)  
  12.     {  
  13.         return;  
  14.     }  
  15.     for(vector<int>::iterator iter = iArray.begin(); iter != iArray.end(); iter ++)  
  16.     {  
  17.         if(pResult.size() < num)  
  18.         {  
  19.             pResult.insert(*iter);  
  20.         }  
  21.         else  
  22.         {  
  23.             multiset<int, greater<int> >::iterator pIter = pResult.begin();  
  24.   
  25.             if(*iter < *(pResult.begin()))  
  26.             {  
  27.                 pResult.erase(pIter);  
  28.                 pResult.insert(*iter);  
  29.             }  
  30.         }  
  31.     }  
  32. }  
  33.   
  34. int main()  
  35. {  
  36.     int iArray[]  = {1,9,7,8,5,3,9,4,2};  
  37.     int len = sizeof( iArray ) / sizeofint );  
  38.     vector< int >  nArray(iArray, iArray + len);  
  39.   
  40.     const unsigned int num = 4;  
  41.     intHeap pResult;  
  42.   
  43.     FindKLeastNumbers(nArray, num, pResult);  
  44.     multiset<int, greater<int> >::iterator iter = pResult.begin();  
  45.   
  46.     while(iter != pResult.end())  
  47.     {  
  48.         cout<<*iter<<" ";  
  49.         iter ++;  
  50.     }  
  51.     cout<<endl;  
  52.     return 0;  
  53.   
  54. }