【转】数组X和数据Y的中位数

1920阅读　0评论2013-04-17　梦醒潇湘love
分类：C/C++


题目：
    设x[1...n]和y[1...n]为两个数组，每个都包含n个已经排好序的数，给出一个求数组x和数组y中所有2n个元素的中位数的O(logn)时间的算法。

思路：
    递归求解该问题，解题规模不断减半，最后剩下4个元素时，得到问题的解。
    本文求的是下中位数，下中位数的特点是：
    （1）当n为奇数时，令n = 2 * m + 1，下中位数是第m + 1小的数，数组中有m个数小于下中位数，有m个数大于下中位数。当数组中的一个数满足以下特点中的任意一个时，认为该数不是下中位数：
            A. 至少有m + 1个数比x大；
            B. 至少有m + 1个数比x小；
    （2）当n为偶数时，令n = 2 * m，下中位数是第m + 1小的数，数组中有m个数小于下中位数，有m - 1个数大于下中位数。当数组中的一个数满足以下特点的任意一个时，认为该数不是下中位数：
            A. 至少有m个数比x大；
            B. 至少有m + 1个数比x小；

    令len_a为数组A中元素个数，len_b为数组B中元素的个数，mid_a是数组A中的下中位数，数组mid_b是B中的下中位数，a = len_a/2，b = len_b / 2。它们满足以下关系：
    （1）len_a和len_b初始时是相等的，经过对数组的处理后，依然相等，奇偶性相同，同理a和b也始终相等；
    （2）mid_a和mid_b的大小不确定，本文例举了mid_a > mid_b的处理方法。

    可以把问题分为以下两种情况：
    （1）len_a和len_b都是偶数，令len_a = 2 * a， len_b = 2 * b， a = b, mid_a > mid_b（初始情况）
    分析：
    在数组A中有a个数字小于mid_a，有a - 1个数字大于mid_b
    在数组B中有b个数字小于mid_b，有b - 1个数字大于mid_b
    mid_a > mid_b：大于mid_a的数字都大于mid_b，小于mid_b的数字都小于mid_a；
                               A和B中至少有a+b+1个数字小于mid_a，至少有a+b-1个数字大于mid_b
                               所有大于mid_a（不包括mid_a）的数字都不是中位数，所有小于mid_b（不包括mid_b）的数字都不是中位数
                               A[1....len_a] -> A[1....a+1] ， B[1....len_b] - > B[b + 1....len_b]

    （2）len_a和len_b都是奇数，令len_a  = 2 * a + 1，len_b = 2 * b + 1， a = b， mid_a > mid_b（初始情况）
    分析：
    在数组A中有a个数字小于mid_a，有a个数字大于mid_a
    在数组B中有b个数字小于mid_b，有b个数字大于mid_b
    mid_a > mid_b：大于mid_a的数字都大于mid_b，小于mid_b的数字都小于mid_a
                               A和B中至少有a+b+1个数字小于mid_a，至少有a+b+1个数字大于mid_b    
                               所有大于mid_a（不包括mid_a）的数字都不是中位数，所有小于mid_b（mid_b）的数字都不是中位数
                               A[1....len_a] - > A[1....a+1]， B[1....len_b] - > B[b + 1....len_b]
    
    经过上文中的分析，最终算法过程如下：
    Step1：分别求出两个数组的中值mid_a和mid_b，比较mid_a和mid_b的大小；
    Step2：如果mid_a = mid_b，那么这个值就是（len_a + len_b）个数中的中位数；
    Step3：如果mid_a > mid_b，A[1....len_a] -> A[1....a]， B[1....len_b] -> B[b + 1....len_b]，递归地对两个新数组求中位数；
    Step4：如果mid_a < mid_b，A[1....len_a] -> A[a + 1....len_a]， B[1....len_b] -> B[1....b]，递归地对两个新数组求中位数；
    Step5：反复Step1-Step4中的递归操作，直到两个数组中剩下的元素一共不超过4个，直接对这4个元素求中位数。
    
    代码如下所示。
  1. //9.3-8
  2. #include <iostream>
  3. using namespace std;

  5. void Print(int *A, int s, int e)
  6. {
  7.     int i;
  8.     for(i = s; i <= e; i++)
  9.         cout<<A[i]<<' ';
  10.     cout<<endl;
  11. }
  12. //最坏情况线性时间的选择
  13. //已经出现很多次了，不解释
  14. int Partition(int *A, int p, int r)
  15. {
  16.     int x = A[r], i = p-1, j;
  17.     for(j = p; j < r; j++)
  18.     {
  19.         if(A[j] <= x)
  20.         {
  21.             i++;
  22.             swap(A[i], A[j]);
  23.         }
  24.     }
  25.     swap(A[i+1], A[r]);
  26.     return i+1;
  27. }
  28. int Select(int *A, int p, int r, int i);
  29. //对每一组从start到end进行插入排序，并返回中值
  30. //插入排序很简单，不解释
  31. int Insert(int *A, int start, int end, int k)
  32. {
  33.     int i, j;
  34.     for(i = 2; i <= end; i++)
  35.     {
  36.         int t = A[i];
  37.         for(j = i; j >= start; j--)
  38.         {
  39.             if(j == start)
  40.                 A[j] = t;
  41.             else if(A[j-1] > t)
  42.                 A[j] = A[j-1];
  43.             else
  44.             {
  45.                 A[j] = t;
  46.                 break;
  47.             }
  48.         }
  49.     }
  50.     return A[start+k-1];
  51. }
  52. //根据文中的算法，找到中值的中值
  53. int Find(int *A, int p, int r)
  54. {
  55.     int i, j = 0;
  56.     int start, end, len = r - p + 1;
  57.     int *B = new int[len/5+1];
  58.     //每5个元素一组，长度为start到end，对每一组进行插入排序，并返回中值
  59.     for(i = 1; i <= len; i++)
  60.     {
  61.         if(i % 5 == 1)
  62.             start = i+p-1;
  63.         if(i % 5 == 0 || i == len)
  64.         {
  65.             j++;
  66.             end = i+p-1;
  67.             //对每一组从start到end进行插入排序，并返回中值,如果是最后一组，组中元素个数可能少于5
  68.             int ret = Insert(A, start, end, (end-start)/2+1);
  69.             //把每一组的中值挑出来形成一个新的数组
  70.             B[j] = ret;    
  71.         }
  72.     }
  73.     //对这个数组以递归调用Select()的方式寻找中值
  74.     int ret = Select(B, 1, j, (j+1)/2);
  75.     //delete []B;
  76.     return ret;
  77. }
  78. //以f为主元的划分
  79. int Partition2(int *A, int p, int r, int f)
  80. {
  81.     int i;
  82.     //找到f的位置并让它与A[r]交换
  83.     for(i = p; i < r; i++)
  84.     {
  85.         if(A[i] == f)
  86.         {
  87.             swap(A[i], A[r]);
  88.             break;
  89.         }
  90.     }
  91.     return Partition(A, p, r);
  92. }
  93. //寻找数组A[p..r]中的第i大的元素，i是从1开始计数，不是从p开始
  94. int Select(int *A, int p, int r, int i)
  95. {
  96.     //如果数组中只有一个元素，则直接返回
  97.     if(p == r)
  98.         return A[p];
  99.     //根据文中的算法，找到中值的中值
  100.     int f = Find(A, p, r);
  101.     //以这个中值为主元的划分，返回中值在整个数组A[1..len]的位置
  102.     //因为主元是数组中的某个元素，划分好是这样的，A[p..q-1] <= f < A[q+1..r]
  103.     int q = Partition2(A, p, r, f);
  104.     //转换为中值在在数组A[p..r]中的位置
  105.     int k = q - p + 1;
  106.     //与所寻找的元素相比较
  107.     if(i == k)
  108.         return A[q];
  109.     else if(i < k)
  110.         return Select(A, p, q-1, i);
  111.     else
  112.         //如果主元是数组中的某个元素，后面一半要这样写
  113.         return Select(A, q+1, r, i-k);
  114.         //但是如果主元不是数组中的个某个元素，后面一半要改成Select(A, q, r, i-k+1)
  115. }
  116. int SelectMid(int *A, int start, int end)
  117. {
  118.     return Select(A, start, end, (end-start+1)/2+1);
  119. }
  120. //返回abcd中第二小的数，已经a<b,c<d
  121. int GetRet(int a, int b, int c, int d)
  122. {
  123.     if(a < c)
  124.     {
  125.         if(c < b)
  126.             return min(b, d);
  127.         return c;
  128.     }
  129.     else
  130.     {
  131.         if(a < d)
  132.             return min(b, d);
  133.         return a;
  134.     }
  135. }
  136. //算法过程
  137. int solve(int *A, int *B, int n)
  138. {
  139.     int ret;
  140.     int startA = 1, startB = 1, endA = n, endB = n;
  141.     while(1)
  142.     {
  143.         if(endA == startA)
  144.             return max(A[startA], B[startB]);
  145.         //如果只剩下4个元素，返回4个元素中第2小的元素
  146.         if(endA - startA == 1)
  147.         {
  148.             ret = GetRet(A[startA], A[endA], B[startB], B[endB]);
  149.             break;
  150.         }
  151.         //分别求得A和B中的中值，这里处理的情况是A和B不是排序的
  152.         //如果A和B是已经排序的，只需mid=A[(start+end)/2]就可以求得中值
  153.         int midA = SelectMid(A, startA, endA);
  154.         int midB = SelectMid(B, startB, endB);
  155. //        cout<<midA<<' '<<midB<<endl;
  156. //        Print(A, startA, endA);
  157. //        Print(B, startB, endB);
  158.         //SELECT算法包含划分的过程，所以可以直接截去不需要一半
  159.         //去掉数组A的前一半和数组B的后一半，注意保证去掉后AB的数组元素个数相等
  160.         if(midA == midB)
  161.         {
  162.             ret = midA;
  163.             break;
  164.         }
  165.         //去掉A的前半和数组B的后半，注意截后两个数组的元素相等
  166.         else if(midA < midB)
  167.         {
  168.             startA = startA + (endA - startA + 1) / 2;
  169.             endB = endB - (endB - startB + 1) / 2;
  170.         }
  171.         //去掉B的前半和数组A的后半，注意截后两个数组的元素相等
  172.         else
  173.         {
  174.             endA = endA - (endA-startA + 1) / 2;
  175.             startB = startB + (endB - startB + 1) / 2;
  176.         }
  177. //        Print(A, startA, endA);
  178. //        Print(B, startB, endB);
  179.     }
  180.     return ret;
  181. }
  182. //测试算法过程
  183. int main()
  184. {
  185.     int n, i;
  186.     while(cin>>n)
  187.     {
  188.         int *A = new int[n+1];
  189.         int *B = new int[n+1];
  190.         //生成随机数据
  191.         for(i = 1; i <= n; i++)
  192.         {
  193.             A[i] = rand() % 100;
  194.             B[i] = rand() % 100;
  195.         }
  196.         //打印生成的数据
  197.         Print(A, 1, n);
  198.         Print(B, 1, n);
  199.         //算法过程
  200.         int ret = solve(A, B, n);
  201.         //输出结果
  202.         cout<<ret<<endl;
  203.         delete A;
  204.         delete B;
  205.     }
  206.     return 0;
  207. }


        原地址：http://blog.csdn.net/mishifangxiangdefeng/article/details/7690461                
            


                                                                                                             梦醒潇湘love
                                                                                                    2013年4月17日  20：48
上一篇：O(n)时间求最接近中位数的k个数
下一篇：数据挖掘之决策树分类模型