两个有序序列的中位数


1.起因


整个事件都是在我完成学校老师布置的一道实验题中发生
(题目在下一节中给出)

在第一次做时,我采用了一个半遍历的做法【时间O(n),空间O(1)】,觉得已经完美了。
而后来舍友跟我说浙大一老哥用二分法做出来了【时间O(log2n),空间O(1)】,让我觉得可以借鉴。

后来,老师却一直强调正确办法是新建一个A和B的并集,再从并集中找中位数。【时间O(2n),空间O(2n)】
这简直让人匪夷所思呀,这不麻烦去了吗?老师是不是没用心做?

直到第二次实验,再仔细读题,发现题目上给的是增序序列!
之前的半遍历法和二分法统统不符合要求,没有考虑到重复元素会合并的特殊情况。

这样一想,老师的方法是对的。花里胡哨的优化,都被“审题”二字打倒。

但我不甘心如此复杂的做法呀,于是……

2.可爱的题目


(2011年考研原题)

一个关键字为L(L>=1)的升序序列S(元素不重复),处在第L/2(向下取整)个位置的数称为S的中位数。
例如,若序列S1=(11,13,15,17,19)则S1的中位数为15,若两个序列的中位数是含它们所有元素的升序序列的中位数。
例如,若S2=(2,4,6,8,20),则S1和S2的中位数是11.
现在有两个等长升序序列A和B:
试设计一个在时间和空间两方面都尽可能高效的算法,找出两个序列A和B(组成的升序序列)的中位数。

3.废弃的两种错误方法


1是一开始的想法,2是网上的目前最优解。
(错误原因是:没考虑到A和B合并后重复元素的影响)

a. 我的思路:半遍历法


让 i(初始化0) 和 j(初始化0) 分别遍历A和B进行循环
(循环条件为 i + j < len - 1)
【等于len也可以,因为两数相等之后又取了一个更大的数,不影响取中位数】

a) 当Data1[i] > Data2[j]时, j++;

b) 当Data1[i] < Data2[j]时, i++;

c) 当Data1[i] == Data2[j]时,i++,j++;

此时,判断Data[i]或者Data[j],谁小谁就是中位数。

/* Start to search */
i = j = k = 0;
int len = list1.GetLen();    // record the length
while (i + j < (2 * len - 1)    // targets found
{
    if (list1.IndexSearch(i) > list2.IndexSearch(j))
    {
        j++;
    }
    else if (list1.IndexSearch(i) < list2.IndexSearch(j))
        i++;
    else
    {
        i++;
        j++;
        k++;
    }
}
cout << "Median of them is ";
cout << (list1.IndexSearch(i) < list2.IndexSearch(j)? list1.IndexSearch(i) : list2.IndexSearch(j)) << endl;    // the smaller one is the median

b.网上最优解:二分法


分别求两个升序序列的 A、B 的中位数 a 和 b,
① 若 a = b, 则已找到两个序列的中位数,返回a
② 若 a < b, 则舍弃序列 A 中较小的一半, 舍弃序列 B 中较大的一半(考虑奇数偶数)
③ 若 a > b, 则舍弃序列 A 中较大的一半, 舍弃序列 B 中较小的一半 (考虑奇数偶数)
重复过程 ① 到 ③ 直到两个序列均只含一个元素为止,返回较小者

int midNum2 ( int* a, int* b, int n ) {
    int s1 = 0, d1 = n-1, s2 = 0, d2 = n-1;
    int m1, m2;
    while ( s1 != d1 || s2 != d2 ) {
        m1 = ( s1 + d1 ) / 2;
        m2 = ( s2 + d2 ) / 2;
        if ( a[m1] == b[m2] ) {
            return a[m1];
        }
        else if ( a[m1] < b[m2] ) {

            if ( (s1 + d1) % 2 == 0 ) { // 元素个数为奇数
                s1 = m1; // 保留中间点
                d2 = m2; // 保留中间点
            }
            else { // 元素个数为偶数
                s1 = m1+1; // 不保留中间点
                d2 = m2; // 保留中间点
            }
        }
        else {
            if ( (s2 + d2) % 2 == 0 ) { // 元素个数为奇数
                s2 = m2; // 保留中间点
                d1 = m1; // 保留中间点
            }
            else { // 元素个数为偶数
                s2 = m2+1; // 不保留中间点
                d1 = m1; // 保留中间点
            }
        }

    } // end of while
    return ( a[s1] < b[s2] )? a[s1]: b[s2];
}

//版权声明:本文为CSDN博主「QiaoDog」的原创文章,遵循CC 4.0 BY-SA版权协议。
//原文链接:https://blog.csdn.net/tao20dage/article/details/88848197

而这两种方法都可以用以下反例证明错误:
A = { 1, 2, 3, 4 } B = { 1, 2, 5, 6 } A∪B = { 1, 2, 3, 4, 5, 6 }
这两种方法得到的结果都是2,而正确答案是3

4.力挽狂澜的突发奇想


当发现题目是想要从A和B的并集中找中位数时,万念俱灰,难不成要接受那个复杂的做法了吗?
那个 “最优解” 二分法,只是不断的舍弃,却不能实现删除重复元素的操作。

但此时,我突然想起了我自己曾经的思路:半遍历……
于是我把循环条件的原理进行了一番深究:
起初,A[i]或者是B[j]代表最小的数;

(i + j)的实际意义就是最小的那个数在并集中移动的次数

当走了 len - 1 次的时候,取A[i]和B[j]中最小值,即(不考虑重复元素时)A和B的中位数。

如果最后一步是A[i] == B[j],也可以通过减去1来实现正常移动 — 详见后面解析。

则此时, (< len - 1)的实际意义就是最小的那个数到达中位数应当移动的次数。

如果此时,将重复元素考虑进去,那么为了表示<最小的那个数在并集中移动的次数>和<最小的那个数到达中位数应当移动的次数>:
我引入了一个新的变量k和m,分别用于记录重复元素总个数和走过的重复元素个数。
当 满足条件A[i] == B[j]后,多执行一条m++; 此时,记录变量m的数值相当于多走的次数
(相当于并集的重复元素的删除操作,且不影响空间效率和时间效率)

于是:
<最小的那个数在并集中移动的次数>可以用(i + j - m)来表示。【因为并集中重复元素不存在】
<最小的那个数到达中位数应当移动的次数>可以用 (ceil(((2 * len) - k )/ 2.f) - 1)来表示。【 ( 2 * len - k ) 就是 并集的实际长度】

至此,让我们再对之前思路进行修改:

让 i(初始化0) 和 j(初始化0) 分别遍历A和B进行循环
(循环条件为 i + j - m != ceil(((2 * len) - k )/ 2.f) - 1)

a) 当A[i] > B[j]时, j++;

b) 当A[i] < B[j]时, i++;

c) 当A[i] == B[j]时,i++;j++;m++;

此时,判断A[i]或者B[j],谁小谁就是中位数。

5.最优解的代码实现


/* Start to search */
    i = j = m = 0;
    int len = list1.GetLen();    // record the length
    k = SameNum(list1, list2);
    while ( i + j - m != ceil(((2 * len) - k )/ 2.f) - 1 )// targets found
    {
        if (list1.IndexSearch(i) > list2.IndexSearch(j))
            j++;
        else if (list1.IndexSearch(i) < list2.IndexSearch(j))
            i++;
        else
        {
            i++;
            j++;
            m++;
        }
    }
    cout << "Median of them is ";
    cout << (list1.IndexSearch(i)<list2.IndexSearch(j)?list1.IndexSearch(i):list2.IndexSearch(j)) << endl;    // the smaller one is the median

至此,整个答案的优化已经完成。

  • 不需要考虑奇偶
  • 考虑到了增序的不重复性,还不需要求并集
  • 时间O(N) 空间O(1)

此时,这个方法是真真正正的最终完美答案!

6.结语


小小的变化,可以有多少种结果; 小小的改善,又隐藏多少的成长。

“无限进步 ”才是我们年轻人心里的信仰,对于那份稳重的热情,拥怀着走下去。


  目录