算法导论习题 9.3-8

瞳人


发布于 Dec. 8, 2016, 11:59 p.m.

0 个评论

Algorithm


题目

设 \( 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 成立:

  1. \( k < n \land Y[n-k] \leqslant X[k] \leqslant Y[n-k+1] \)
  2. \( k ==n \land X[k] \leqslant Y[1] \)

则 \( X[k] \) 是中位数,否则中位数在 \( Y \) 中,则二分查找 \( Y[k] \),使得如下关系1 或者 2 成立:

  1. \( k < n \land X[n-k] \leqslant Y[k] \leqslant X[n-k+1] \)
  2. \( 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


Leave a Comment:

博客搜索

友情链接

公告

本博客代码已经公布在 Github 上,欢迎交流指正。

QQ 邮箱对 mailgun 不太友好, 所以使用 QQ 邮箱的评论, 可能会无法及时收到邮件。我会尽快寻找其他解决方案的。

本人现在独自使用 linode vps, 20 美元/月, 感觉压力大, 如果有意一起合租, 可以联系我. 在我的任意一篇文章下面留言即可. 关于使用方式, 现在倾向于使用 docker.