> For the complete documentation index, see [llms.txt](https://windmising.gitbook.io/introduction-to-algorithms/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://windmising.gitbook.io/introduction-to-algorithms/introduction-3/exercise.md).

# 练习题

## 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)之间（包括这两点）


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://windmising.gitbook.io/introduction-to-algorithms/introduction-3/exercise.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.