面試100題--05查找TPO k

            面試題100---05 查找TOPK

從數組中找出最小的K個數
 最笨的方法：對原數組進行排序，這樣的話其復雜度為o(nlogn)
 下面介紹一個o(n+logk n)的方法 ，最后再介紹一個方法，實現對k數組不需要排序，但是需要一個輔助堆棧
 
 新建一個輔助堆棧k,插入數組時，若k數組中的數組，不足k。則直接插入元素。
 若k數組中的數目。已經為k，則需要找出數組中的最大值。并與要插入的值x進行比較，若值x大于最大值，則忽略。否則將最大值替換為x。
 上述說明的方法，其復雜度為o(n + logK * n)。
 使用一個堆，來存放k數組,以盡可能快地進行max運算。

#include <iostream>
#include <vector>
#include <iterator>
#include <set>
 using namespace std ;
 typedef multiset <int , greater<int> > heap ;
 

 const int K = 5 ;
 const int N = 10 ;
 int main()
 {
    int i , x;
    vector<int> vdata ; //存儲數據元素 
   heap kdata ; //存儲k個元素  
  
 
 
    for( i = 0 ;i < N ; i++ )
    {
         cin>>x ;
         vdata.push_back(x) ; 
    }
    
    vector<int>::const_iterator iter = vdata.begin() ;
    for(;iter != vdata.end() ; iter++)
    {
         if(kdata.size() < K)
         {
           kdata.insert(*iter) ; //直接插入元素                                  
         } 
         //kdata中存儲的元素個數大于K
         else      
         {
                heap::iterator iterFirst = kdata.begin() ;
                if(*iter < *iterFirst)
                 {
                   kdata.erase(iterFirst) ;
                   kdata.insert(*iter) ;        
                 }
                   
         }      
    }
    heap::iterator iters = kdata.begin() ;
    for(; iters != kdata.end() ;iters++)
    {
          cout<<*iters<<" " ;
    }
  
    system("pause") ;      
    return 0 ;   
 }

posted on 2011-05-16 11:22 kahn 閱讀(283) 評論(0)  編輯 收藏 引用 所屬分類: 算法相關