练习题

9.1 最小值和最大值

9.2 以期望线性时间做选择

9.2-3

RANDOMIZED-SELECT(A, p, r, i)
 1    while true
 2        if p = r
 3            then return A[p]
 4        q <- RANDIMIZED-PARTITION(A, p, r)
 5        k <- q - p + 1
 6        if i = k
 7            then return A[q]
 8        else if i < k
 9            then q <- q-1
10        else
11            q <- q + 1
12            i <- i - k

9.2-4

    A = {3, 2, 9, 0, 7, 5, 4, 8, 6, 1}
==> A = {3, 2, 0, 7, 5, 4, 8, 6, 1, 9}
==> A = {3, 2, 0, 7, 5, 4, 6, 1, 8, 9}
==> A = {3, 2, 0, 5, 4, 6, 1, 7, 8, 9}
==> A = {3, 2, 0, 5, 4, 1, 6, 7, 8, 9}
==> A = {3, 2, 0, 4, 1, 5, 6, 7, 8, 9}
==> A = {3, 2, 0, 1, 4, 5, 6, 7, 8, 9}
==> A = {2, 0, 1, 3, 4, 5, 6, 7, 8, 9}
==> A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
==> A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
==> A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

9.3 最坏情况线性时间的选择

9.3-3

先中SELECT选择中值，再用这个中值进行划分，代码见算法导论-9.3-3

QUICKSORT(A, p, r)
1    if p > r
2        then return
3    i <- (r-p+1) / 2
4    x <- SELECT(A, p, r, i)
5    q <- PARTITION(A, p, r, x) //以x为主元的划分
6    QUICKSORT(A, p, q-1)
7    QUICKSORT(A, q+1, r)

9.3-5

SELECT(A, p, r, i)
1    if p = r
2        then return A[p]
3    x <- MEDIAN(A, p, r)
4    q <- PARTITION(A, p, r, x) //以x为主元的划分
5    k <- q - p + 1
6    if i = k
7        then return A[q]
8    else if i < k
9        then return SELECT(A, p, q-1, i)
10    else return SELECT(A, q+1, r, i-k)

9.3-6

令每个子集合的元素个数为t = n / k，A[j]是数组A中下标为j的元素，A(j)是数组是第j大的元素

则所求的k分位数是指A(t)，A(2t)，A(3t)，……，A((k-1)t)

按顺序依次求这k-1个数的运行时(k-1)*n

要使运行时间为O(nlgk)，改进方法是不要依次寻找这k-1个数，而是借用二分的方法来找。

先找第k/2个分位数，再以这个分位数为主元把数组分为两段，分别对这两段来找分位数，这个时候找的范围变小了，效率也就提高了

见算法导论-9.3-6

9.3-7

step1：求出数组的中位数的值O(n)

step2：计算数组每个数与中位数差的绝对值，存于另一个数组B中O(n)

step3：求出数组B中第k小的数ret O(n)

step4：计算数组S中与ret差的绝对值小于ret的数并输出O(n)

其中，step4也可以通过划分的方法找出数组S中与ret差的绝对值小于ret的数

代码见算法导论-9.3-7

9.3-8

递归求解该问题，解题规模不断减半，最后剩下4个元素时，得到问题的解

分别取两个数组的中值minA和minB进行比较

如果minA=minB，那么这个值就是结果

否则，小的那个所在的数组去掉前面一半，大的那个去掉后面一半。（对于两个数组的中值，共有n-1个元素，有n个元素比它大。但是对于min(minA,minB)，最多只有n-2个元素比它小，所以一定不是所求的结果，同理去掉大的一半）

然后对剩余的两个数组，用同的方法求它们的中值，直到两个数组一共剩下4个元素

代码见算法导论-9.3-8

9.3-9

这题其实挺简单的，就是不一定能找到这个规律。

为了简化这道题，不考虑点的y坐标，假设所有的点都在一条与管道垂直的线上

假如有两个点AB，分别在管道l的上下，那么不管这条管道在什么位置（只要在AB之间），d[Al]+d[bl]=d[AB]。

根据以上规律，把每两个点分为一组，第i组中的点是（第i大的点，第i小的点），只要管道在每组的两个点之间，就能保证长度总和最小。

由以上推理得出答案：

令所以x作为的中值为s(i)，

如果点的个数是奇数，管道过s(i)点

如果点的个数是偶数，管道位于点s(i)和s(i+1)之间（包括这两点）