Liny_@NotePad

沉迷ACG中

分治法求第K大元素

YOYO posted @ 2009年4月29日 08:02 in 【算法】与【数据结构】 with tags 分治 , 5394 阅读

 k大元素不就是第(n-k+1)小元素么 = =

  1. #include<iostream>
  2. #include<algorithm>
  3. using namespace std;
  4.  
  5. /***************************************
  6. * 选择第k小元素算法
  7. *
  8. * 输入：元素数组A[]，元素个数n，求的k
  9. * 输出：第k小元素
  10. ***************************************/
  11. template<class Type>
  12. Type select(Type A[], int n, int k){
  13.         int i,j,s,t;
  14.         Type m,*p,*q,*r;
  15.         if(n<38){                     //     如果元素个数小于38：则直接排序
  16.                 sort(A,A+n);
  17.                 return A[k-1];
  18.         }
  19.         p = new Type[3*n/4];
  20.         q = new Type[3*n/4];
  21.         r = new Type[3*n/4];
  22.         for( i=0; i<n/5; i++){  //        五个一组，把每组的中值元素存放进数组p
  23.                 mid(A,i,p);
  24.         }
  25.         m = select(p, i, i/2+i%2);      //    递归调用，取得中值元素存入m
  26.         i = j = s = 0;
  27.         for( t=0; t<n; i++){    //  按<m、=m、>m把数组分成三组
  28.                 if(A[t]<m){
  29.                         p[i++] = A[t];
  30.                 }else{
  31.                         if(A[t]==m){
  32.                                 q[j++] = A[t];
  33.                         }else{
  34.                                 r[s++] = A[t];
  35.                         }
  36.  
  37.                 }
  38.         }
  39.         if(i>k){                                //      若k<i，则该元素就在数组p中，进入p继续查找
  40.                 return select(p,i,k);
  41.         }else{
  42.                 if(i+j>=k){               //   若i<k<i+j，则该元素在q数组中，即值为m
  43.                         return m;
  44.                 }else{        //        若k>i+j，则该元素在r数组中，进入r继续寻找
  45.                         return select(r,s,k-i-j);
  46.                 }
  47.         }
  48. }
  49.  
  50. /***************************************
  51. * 计算中值元素
  52. *
  53. * 输入：元素数组A[]，组号i
  54. * 输出：存放中值元素的数组p[]
  55. ***************************************/
  56. template<class Type>
  57. void mid(Type A[], int i, Type p[]){
  58.         int k = 5*i;
  59.         if(A[k]>A[k+2]){
  60.                 swap(A[k], A[k+2]);
  61.         }
  62.         if(A[k+1]>A[k+3]){
  63.                 swap(A[k+1], A[k+3]);
  64.         }
  65.         if(A[k]>A[k+1]){
  66.                 swap(A[k],A[k+1]);
  67.         }
  68.         if(A[k+2]>A[k+3]){
  69.                 swap(A[k+2],A[k+3]);
  70.         }
  71.         if(A[k+1]>A[k+2]){
  72.                 swap(A[k+1],A[k+2]);
  73.         }
  74.         if(A[k+4]>A[k+2]){
  75.                 p[i] = A[k+2];
  76.         }else{
  77.                 if(A[k+4]>A[k+1]){
  78.                         p[i] = A[k+4];
  79.                 }else{
  80.                         p[i] = A[k+1];
  81.                 }
  82.         }
  83. }
  84.  
  85. int main(){
  86.         int n,m;
  87.  
  88.         cout<<"请输入数组元素个数：";
  89.         cin>>n;
  90.        
  91.         cout<<"请输入要求的k：";
  92.         cin>>m;
  93.        
  94.         int *A = new int[n];
  95.         int i;
  96.  
  97.         cout<<"请输入数组元素："<<endl;
  98.         for(i=0;i<n;i++){
  99.                 cin>>A[i];
  100.         }
  101.        
  102.         cout<<"第"<<m<<"大元素是：";
  103.         cout<<select(A,n,n-m+1)<<endl;    // 输出第(n-m+1)小元素<=>第m大元素
  104.  
  105.         return 0;
  106. }
Small_feed 评论 (0)

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter