Chinaunix首页 | 论坛 | 博客
  • 博客访问: 2115143
  • 博文数量: 249
  • 博客积分: 1305
  • 博客等级: 军士长
  • 技术积分: 4733
  • 用 户 组: 普通用户
  • 注册时间: 2011-12-17 10:37
个人简介

不懂的东西还有很多,随着不断的学习,不懂的东西更多,无法消灭更多不懂的东西,那就不断的充实自己吧。 欢迎关注微信公众号:菜鸟的机器学习

文章分类

全部博文(249)

文章存档

2015年(1)

2014年(4)

2013年(208)

2012年(35)

2011年(1)

分类: C/C++

2013-04-17 20:48:35


题目:
    设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;

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


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


                                                                                                             梦醒潇湘love
                                                                                                    2013年4月17日  20:48
阅读(1926) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~