算法导论 Exercises 9.3-8 - GoAgent - 博客园

算法导论 Exercises 9.3-8 - GoAgent - 博客园

Problem Description:

Let X[1...n] and Y[1...n] be two arrays, each containing n numbers already in sorted order.

Give an O(lgn)-time algorithm to find the median of all 2n elements in array X and Y.

问题描述：

X和Y是两个长度均为n的已排序数组，现要求以O(lgn)的时间复杂度找到两个数组中所有2n个数的中值。

（注：这里中值被定义为：对于奇数个数，排序后中间那个，或者对于偶数个数，排序后中间两个数下标较小的那个）

问题升级：

题目中假设了两个数组长度相等，并且找中值。

这里修改一下题目，假设两个数组长度不一定相等，分别为m和n，要求以O(lgm + lgn)的时间复杂度找到m+n个数中的第i个数。

先解决一般情况，再将原题作为一种特殊情况来处理。

 

解决方案：

如上图所示的两个已排序数组（假设为单调非减），其中aMid = (aBeg + aEnd) / 2是数组中值的下标。

{a1}是数组a中a[aBeg]至a[aMid]段的元素的集合，{a2}是数组a中a[aMid + 1]至a[aEnd]段的元素的集合。同理{b1}、{b2}如图所示。

 

假设a[aMid] <= b[bMid]（a[aMid] > b[bMid]的情况与之类似），则有：

{a1}<={a2} {a1}<={b2}

即对于{a1}中的任意元素，在a、b中不小于它的数至少有(aEnd - aMid) + (bEnd - bMid) + 1个

所以对于{a1}中的任意元素，在a、b中小于它的数至多有

[(aEnd - aBeg + 1) + (bEnd - bBeg + 1)] - [(aEnd - aMid) + (bEnd - bMid) + 1]

=(aMid - aBeg) + (bMid - bBeg) + 1个......①

同理，{b2}>={b1} {b2}>={a1}

即对于{b2}中的任意元素，在a、b中不大于它的数至少有(bMid - bBeg) + (aMid - aBeg) + 1

=(aMid - aBeg) + (bMid - bBeg) + 1个......②

由①、②可知：

如果i <= (aEnd - aMid) + (bEnd - bMid) + 1,那第i个数一定不在{b2}中。

此时只需在{a1}、{a2}、{b1}中继续找第i个数就可以了。

（当i == (aEnd - aMid) + (bEnd - bMid) + 1时，只有在a[aMid] == b[bMid]时，第i个数等于a[aMid]或者b[bMid]，

此时虽然b[bMid]在{b2}中，但由于a[aMid]不在{b2}中，所以不影响我们"第i个数一定不在{b2}中"的判断）

如果i > (aEnd - aMid) + (bEnd - bMid) + 1,那第i个数一定不在{a1}中。

此时只需在{a2}、{b1}、{b2}中继续找第i - (aMid - aBeg + 1)个数就可以了。

同理在a[aMid] > b[bMid]时，可以得出类似的结论，只是a、b两个数组的角色互换。

 

由上面的分析，每次递归可以丢弃掉其中一个数组一半的元素直至递归结束。

递归结束的条件是其中一个数组已经为空，此时在另外一个数组里面直接找第i个数就可以了。

因此本算法的时间复杂度是O(lgm + lgn)的。

Read full article from 算法导论 Exercises 9.3-8 - GoAgent - 博客园