鸿 网 互 联 www.68idc.cn

当前位置 : 服务器租用 > 手机系统开发 > J2ME > >

两个数组的中位数

来源:互联网 作者:佚名 时间:2015-09-25 05:46
Code: #includeiostream using namespace std; void sort( int x[], int n) { int temp; int i; int j; for (i=1;in;++i) { temp=x[i]; for (j=i-1;j=0;--j) { if (x[j]temp) { x[j+1]=x[j]; } else { break ; } } x[j+1]=temp; } } int median( int x[], in

 

Code:
  1. #include <iostream>  
  2. using namespace std;  
  3.   
  4. void sort(int x[], int n)  
  5. {  
  6.     int temp;  
  7.     int i;  
  8.     int j;  
  9.       
  10.     for (i = 1; i < n; ++i)  
  11.     {  
  12.         temp = x[i];  
  13.         for (j = i - 1; j >= 0; --j)  
  14.         {  
  15.             if (x[j] > temp)  
  16.             {  
  17.                 x[j + 1] = x[j];  
  18.             }  
  19.             else  
  20.             {  
  21.                 break;  
  22.             }  
  23.         }         
  24.         x[j + 1] = temp;  
  25.     }  
  26. }  
  27.   
  28. int median(int x[], int y[], int n)  
  29. {  
  30.     int first_x = 0;  
  31.     int first_y = 0;  
  32.     int last_x = n - 1;  
  33.     int last_y = n - 1;  
  34.     int count = 0;  
  35.     int mid_x;  
  36.     int mid_y;  
  37.       
  38.     int z[4];  
  39.       
  40.     while (last_x - first_x > 1 || last_y - first_y > 1)  
  41.     {  
  42.         mid_x = (first_x + last_x) / 2;  
  43.         mid_y = (first_y + last_y) / 2;  
  44.           
  45.         if (x[mid_x] <= y[mid_y])  
  46.         {  
  47.             count += (mid_x - first_x);  
  48.             first_x = mid_x;  
  49.             last_y = mid_y;  
  50.         }  
  51.         else  
  52.         {  
  53.             count += (mid_y - first_y);  
  54.             first_y = mid_y;  
  55.             last_x = mid_x;  
  56.         }  
  57.     }  
  58.       
  59.     int number;  
  60.     for (number = 0; first_x <= last_x; ++first_x)  
  61.     {  
  62.         z[number++] = x[first_x];  
  63.     }  
  64.       
  65.     for (; first_y <= last_y; ++first_y)  
  66.     {  
  67.         z[number++] = y[first_y];  
  68.     }  
  69.       
  70.     sort(z, number);  
  71.       
  72.     return z[n - count - 1];  
  73. }  
  74.   
  75. int main(int argc, char *argv[])  
  76. {  
  77.       
  78.     return 0;  
  79. }  

 

网友评论
<