首页 团队成员,Ven_殃雾的文章

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],则算走了len次,但因为取最小值,所以不影响结果。

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

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

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

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

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

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

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

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

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

5.最优解的代码实现


/* Start to search */
i = j = k = 0;    // k For recording Duplicate numbers
int len = list1.GetLen();
while (i + j - k < ((2 * len) - k )/ 2 - 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

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

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

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

6.结语


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

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




文章评论

目录