Question

9.1 最小值和最大值

9.1-1

见 算法导论 9.1-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) 之间（包括这两点）