Chinaunix首页 | 论坛 | 博客
  • 博客访问: 121174
  • 博文数量: 53
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 620
  • 用 户 组: 普通用户
  • 注册时间: 2014-08-24 16:22
文章存档

2014年(53)

我的朋友

分类: C/C++

2014-09-04 22:11:36

设两个有序数组的长度均为n,求它们组成的2n长的数组的中位数。

首先说明下中位数的定义:
统计学名词,当变量值的项数N为奇数时,处于中间位置的变量值即为中位数;当N为偶数时,中位数则为处于中间位置的2个变量值的平均数。
中位数有个性质:在中位数两侧去掉任意数量的数后,中位数不变

为了简化,先假设n为奇数,那么A[n/2]是中位数,假设
1. A[n/2]>B[n/2],那么A[n/2+1]...A[n-1]都大于A[0]...A[n/2]并且大于B[0]...B[n/2],而这些数加起来有n+1个,所以A[n/2+1]...A[n-1]大于所求的中位数;同理,B[0]...B[n/2-1]小于B[n/2]...B[n-1]并且小于A[n/2]...A[n-1], 而这些数加起来有n+1个,所以B[0]...B[n/2-1]小于所求的中位数。
所以,利用中位数性质,问题缩小成在A[0]...A[n/2]和B[n/2]...B[n-1]这两个有序数组中找中位数,可用递归。
2. A[n/2]==B[n/2],那么A[n/2]就刚好位于n-1或n的位置上,所以它就是中位数
3. A[n/2]
由此扩展一下,当n为偶数时,((double)A[n/2]+(double)A[n/2+1])/2为A的中位数,设A_mid为A[]的中位数,B_mid为B[]的中位数,那么:
1. 当A_mid>B_mid时,A[n/2+1, n-1]都不可能出现中位数,同理B[0, n-1-n/2-1]也不可能出现中位数,所以排除这两个,可能出现中位数的地方是在:A[0,n/2]和B[n-1-n/2,n-1]
2. 当A_mid==B_mid时, 中位数是A_mid
3. 
当A_mid时, 对称不表

由此我们可以统一奇数和偶数的公式为:
假设求有序数组A[la, ra]和B[lb, rb]组成的有序数组的中位数,两个数组的长度相等且为length,那么:
若A_mid>B_mid,
    变成求A[la,la+length/2]和B[rb-length/2,rb]的中位数
若A_mid     变成求A[ra-length/2, ra]和B[lb,lb+length/2]的中位数
若A_mid==B_mid,

     中位数就是A_mid

因此可得code:

  1. int *A;
  2. int *B;
  3. double f(int la,int ra,int lb,int rb){
  4.     if(la==ra)
  5.         return ((double)A[la]+(double)B[lb])/2;
  6.     else if((ra-la)==1){
  7.         double x=A[la]>=B[lb]?A[la]:B[lb];
  8.         double y=A[ra]>=B[rb]?B[rb]:A[ra];
  9.         return (x+y)/2;
  10.     }
  11.     else{
  12.         int length=ra-la+1;
  13.         double m,n;
  14.         if(length%2==0){
  15.             m=((double)A[(la+ra)/2]+(double)A[(la+ra)/2+1])/2;
  16.             n=((double)B[(lb+rb)/2]+(double)B[(lb+rb)/2+1])/2;
  17.         }
  18.         else{
  19.             m=A[(la+ra)/2];
  20.             n=B[(lb+rb)/2];
  21.         }
  22.         if(m>n)
  23.             return f(la,la+length/2,rb-length/2,rb);
  24.         else if(m<n)
  25.             return f(ra-length/2,ra,lb,lb+length/2);
  26.         else
  27.             return m;
  28.     }
  29. }

  30. double findMedianSortedArrays(int a[], int m, int b[], int n) {
  31.     A=a;
  32.     B=b;
  33.     return f(0,m-1,0,n-1);
  34. }

还有一个简化的中位数的定义,就是无论n是奇数还是偶数,A[n]的中位数就是A[n/2]

这样,无论n为奇数偶数,可得公式
1. 当A[n/2]>B[n/2]时,
    变成求以A[0]开始长度为n-n/2的新数组和以B[n/2]开始,长度为n-n/2的新数组的中位数
2. 当
A[n/2]>B[n/2]时,
    和1对称
3. 当A[n/2]==B[n/2]时
    A[n/2]就是中位数

可得code:

  1. int findMedianSortedArrays( int a[], int b[], int length)
  2. {
  3.     if (length == 1)
  4.         return a[0];
  5.           
  6.     int mid = length/2;
  7.     if (a[mid] == b[mid])
  8.         return a[mid];
  9.     else if (a[mid]<b[mid])
  10.         return findMedianSortedArrays( &a[mid], &b[0], length-mid );
  11.     else
  12.         return findMedianSortedArrays( &a[0], &b[mid], length-mid );
  13. }







阅读(1021) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~