jake1036

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

   寻求最大的k个数

 方法一: 使用partition函数,将数组分为两组。
            (1)分为两个组,sa和sb。
            (2)若sa组的个数大于K,则继续在sa分组中找取最大的K个数字 。
            (3)若sa组中的数字小于K ,其个数为T,则继续在sb中找取 K-T个数字 。
   具体代码实现:
        

#include <iostream>
  
using namespace std ;
  
const int N = 8 ; 
  
const int K = 4 ;
  
int partition(int  a[] ,int low , int high) 
  
{
      
int i = low - 1 ;
      
int j = low;
      
      
while(j < high)
      
{
         
if(a[j] >=  a[high])
         
{
           swap( a[i
+1] , a[j]) ;        
           i
++   ;     
         }

         j
++ ;      
      }

      
//最后处理a[high]
      swap(a[i+1] , a[high]) ;  
      
return i + 1;     
  }

  
  
  
int findk(int  a[] , int low , int high , int k)
  
{
      
if(low < high)
      
{
        
int q = partition(a , low , high) ;
        
        
int len = q - low + 1 ; //表示第几个位置 
        if(len == k)
         
return q ; //返回第k个位置
        else if(len < k) 
         
return findk(a , q + 1 , high , k - len) ;   
       
else
        
return findk(a , low , q - 1, k ) ;
      }

  }

  
  
int main()
  
{
    
int a[N] = {5 ,2 ,66 ,2311 ,1 ,4 ,55} ;
    findk(a , 
0 , N - 1 , K) ;  
    
    
for(int i = 0 ; i < K ; i++)
      cout
<<a[i]<<endl ;
    
    system(
"pause") ;  
    
return 0 ;    
  }
 

 方法二 :
   此种方法为常用方法,建立一个大小为K的堆。每次遍历数组时,需要判断是否需要加入堆中。
   堆中存储着的是最大的k个数字,但是若是需要插入堆中,则需要对堆进行调整时间为o(log k)。
   全部的时间复杂度为o(n * log k)。
  
  这种方法当数据量比较大的时候,比较方便。因为对所有的数据只会遍历一次,第一种方法则会多次遍历
  数组。 如果所查找的k的数量比较大。可以考虑先求出k` ,然后再求出看k`+1 到 2 * k`之间的数字,然后
  一次求取。
 
 方法三:
     利用二分的方法求取TOP k问题。
     首先查找 max 和 min,然后计算出 mid = (max + min) / 2
     该算法的实质是寻找最大的K个数中最小的一个。
  
    代码如下:
    

#include <iostream>
 
using namespace std ; 
 
const int N = 8 ;
 
const int K = 4 ;
 
 
/*
 利用二分的方法求取TOP k问题。
 首先查找 max 和 min,然后计算出 mid = (max + min) / 2
 该算法的实质是寻找最大的K个数中最小的一个。 
 
 
 
*/

 
 
int find(int * a , int x) //查询出大于或者等于x的元素个数 
 {
     
int sum = 0 ;
     
     
for(int i = 0 ; i < N ; i++ )
     

        
if(a[i] >= x)
          sum
++ ;                
     }

      
return sum ;
 }

 
 
 
 
 
int getK(int * a , int max , int min) //最终max min之间只会存在一个或者多个相同的数字 
 {
     
while(max - min > 1)             //max - min的值应该保证比两个最小的元素之差要小 
      {
        
int mid = (max + min) / 2 ;
        
int num = find(a , mid) ;    //返回比mid大的数字个数 
        if(num >= K)                 //最大的k个数目都要比min值大 
           min = mid ;               
        
else
           max 
= mid  ;
      }

      cout
<<"end"<<endl;
      
return min ;
 }

 
 
int main()
 
{
   
int a[N] = {542 ,5 ,11 ,554 ,65 ,33 ,2} ;  
   
int x = getK(a , 554 , 2) ; 
   cout
<<x<<endl ; 
   getchar() ; 
   
return 0 ;    
 }
















posted on 2011-07-07 20:43 kahn 阅读(1329) 评论(1)  编辑 收藏 引用

Feedback

# re: 编程之美-2.5寻求最大的K个数[未登录] 2014-09-24 22:58 xixi

你确定以上代码可以运行?
呵呵  回复  更多评论   



只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理