算法导论习题 9.3-8
由 瞳人
发布于 Dec. 8, 2016, 11:59 p.m.
0 个评论
题目
设 \( X[1..n ] \) 和 \( Y[1.. n ] \) 为两个数组，每个都包含 \( n \) 个已排好序的数。给出一个 求数组 \( X \) 和 \( Y \) 中所有 \( 2n \) 个元素的中位数的 \( \mathit{O} (\mathrm{lg} \ n) \) 时间的算法。
思路
不失一般性，我们这里仅考虑下中位数。我们不妨先设中位数在\( X \) 中，且为第 \( k \) 项 \( X[k] \)。 由于 \( X \) 已经有序，所以其中有 \( k \) 个元素小于等于 \( X[k] \)，\( n - k \) 个元素大于等于 \( X[k] \)。 又因为 \( X[k] \) 是中位数，所以共有 \( n \) 个元素小于等于 \( X[k] \)，\( n \) 个元素大于等于 \( X[k] \) 。 因此，在 \( Y \) 中，有 \( n - k \) 个元素小于等于 \( X[k] \)，\( k \) 个元素大于等于 \( X[k] \)。又因为 \( Y \) 已经有序了，因此上述关系就等价于 \( Y[n-k] \leqslant X[k] \leqslant Y[n-k+1] \)。注意当 \( k = n \) 时，不存在 \( Y[0] \)，我们只需判断 \( X[k] \leqslant Y[1] \)。
如果上述 \( X[k] \) 不是中位数，那么上述关系将不成立。我们假设 \( X[k'] \) 为中位数，并且 \( k' < k \)。那么此时有 \( Y[n-k+1] \leqslant Y[n-k'] \leqslant X[k'] < X[k] \)。同理，可得若 \( X[k''] \) 为中位数，并且 \( k < k'' \)。 那么此时有 \( X[k] < X[k''] \leqslant Y[n-k''+1] \leqslant Y[n-k] \)。
因此，我们可以使用二分法来查找是否存在 \( X[k] \) 使得如下关系1 或者 2 成立：
- \( k < n \land Y[n-k] \leqslant X[k] \leqslant Y[n-k+1] \)
- \( k ==n \land X[k] \leqslant Y[1] \)
则 \( X[k] \) 是中位数，否则中位数在 \( Y \) 中，则二分查找 \( Y[k] \)，使得如下关系1 或者 2 成立：
- \( k < n \land X[n-k] \leqslant Y[k] \leqslant X[n-k+1] \)
- \( k ==n \land Y[k] \leqslant X[1] \)
这样得到的 \( Y[k] \) 是中位数。因为每次二分查找的时间复杂度均为 \( \mathit{O} (\mathrm{lg} \ n) \)。所以 该算法复杂度为 \( \mathit{O} (\mathrm{lg} \ n) \)。
代码
Python 代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 | # coding=utf-8 import random __author__ = 'answ.me' def two_array_median(x, y): n = len(x) - 1 median = find_median(x, y, n, 1, n) if median is None: median = find_median(y, x, n, 1, n) return median def find_median(a, b, n, low, high): if low > high: return None else: k = int((low + high) / 2) if k == n and a[n] <= b[1]: return a[n] elif k < n and b[n-k] <= a[k] <= b[n-k+1]: return a[k] elif a[k] > b[n-k+1]: return find_median(a, b, n, low, k-1) else: return find_median(a, b, n, k+1, high) def sorted_random_array(n): array = [0] array.extend(random.sample(range(100), n)) array.sort() return array def test(n): x = sorted_random_array(n) y = sorted_random_array(n) print('X: %s\nY: %s' % (x[1:], y[1:])) print('obtained median:', two_array_median(x, y)) x.extend(y) x.sort() print('expected median:', x[n+1]) if __name__ == '__main__': test(10) |
0 Comments