面试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 阅读(258) 评论(0)  编辑 收藏 引用 所属分类: 算法相关