算法导论 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 - 博客园
No comments:
Post a Comment