【\*习题2-13】
原始讲义 · 非增强校订版 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照
## 【\*习题2-13】
(13 分)已知数组 A 中有 n 个非负元素，每个元素 A[i]< 2n。请设计一个时间上尽可能高效的算法，求出数组 A 中第 k小的元素。
例：A = {1,2,1,2, 3,3}，n = 6，k = 3，按照升序得到 {1, 1,2, 2, 3, 3}，所以第 k 小的元素是 2(第 3、4 大元素都是2），输出2。
(1)给出算法的基本设计思想。
(2)根据设计思想，采用C、C++或Java语言描述算法，关键之处给出注释。
(3)说明你所设计算法的时间复杂度和空间复杂度。
## 【习题2-14】
(13 分）已知数组 A 中有 n 个元素（可能重复），每个元素2n ≤A[i] < 3n。请设计一个尽可能高效的算法，从小到大输出A数组中的元素（重复元素只输出一次）。
例：A={13,17,16,14,13,13}，n= 6，出现的元素是13、17、16、14，所以从小到大依次输出：13、14、16、17。
(1) 给出算法的基本设计思想。
(2)根据设计思想，采用C、C++或Java语言描述算法，关键之处给出注释。
(3)说明你所设计算法的时间复杂度和空间复杂度。
## 【习题2-15】
(15 分)已知一个整数序列 A =(a0， a1……, an-1)，其中 0 ≤ a < n（0 ≤i < n)。从数组中选择一些数，要求选择的数中任意两数差的绝对值<=k。设计一个在时间上尽可能高效的算法输出最多可能选择的元素个数。要求：
(1)给出算法的基本设计思想。
(2)根据设计思想，采用C、C++或Java 语言描述算法，关键之处给出注释。
(3)说明你所设计算法的时间复杂度和空间复杂度。
## 【习题2-16】
(15分）在数组中，某个数字减去它右边的数字得到一个数对之差。求所有数对之差的最大值。例如，在数组{2,4,1,16,7,5,11,9}中，数对之差的最大值是11，是16 减去5的结果。设计一个在时间上尽可能高效的算法输出所有数对之差的最大值。
<!-- page 25 -->
(1)给出算法的基本设计思想。
(2)根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
(3)说明你所设计算法的时间和空间复杂度。
## 【习题2-17】
(15 分）已知一个整数升序序列 A =(a0， a1…, an-1)。设计一个尽可能高效的算法返回整数x 出现的次数。函数原型为： int countOccurrences(int A[], int n, int x)。
(1)给出算法的基本设计思想。
(2)根据设计思想，采用C语言描述算法，关键之处给出注释。
(3)说明你所设计算法的时间复杂度和空间复杂度。
## 2.5.2 真题
## 【2010年42题】
(13分）设将n（n>1)个整数存放到一维数组R中。试设计一个在时间和空间两方面都尽可能高效的算法。将R中保存的序列循环左移p（0<p<n）个位置，即将 R中的数据由(X0，X₁…,Xn-1)变换为(Xp，Xp+1……,Xn-1,X₀,X1……,Xp-1)。要求:
(1)给出算法的基本设计思想。
(2)根据设计思想，采用C、C++或Java 语言描述算法，关键之处给出注释。
(3)说明你所设计算法的时间复杂度和空间复杂度。
## 【2011年42题】
(15 分）一个长度为L(L≥1)的升序序列S，处在第[L/2] 个位置的数称为S的中位数。例如，若序列S1 =(11,13，15,17,19)，则S1 的中位数是 15，两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若 S2 =(2,4,6,8，20)，则S1 和S2的中位数是11。现在有两个等长升序序列A和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数。要求：
(1)给出算法的基本设计思想。
(2)根据设计思想，采用C、C++或Java 语言描述算法，关键之处给出注释。
(3)说明你所设计算法的时间复杂度和空间复杂度。
## 【2013年41题】
(13 分）已知—个整数序列 A = (a0, a1……, an-1)，其中 0 ≤ a < n(0 ≤i < n)。若存在 ap1 = ap2 =..= apm = x 且 m>n/2(0 ≤ pk < n, 1 ≤ k ≤ m)，则称 x 为 A的主元素。例如 A = (0, 5, 5, 3, 5, 7, 5,5)，则 5 为主元素；又如 A = (0, 5,5,3,5,1,5,7)，则 A 中没有主元素。假设 A 中的 n 个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出 A的主元素。若存在主元素，则输出该元素；否则输出-1。要求:
(1) 给出算法的基本设计思想。
(2)根据设计思想，采用C、C++或Java语言描述算法，关键之处给出注释。
(3)说明你所设计算法的时间复杂度和空间复杂度。
## 【2016年43题】
（13 分）已知由 n(n ≥ 2)个正整数构成的一个集合 A = {ak|0 ≤ k < n}，将其划分为两个不相交的子集 A1和 A2，元素个数分别是 n1 和 n2，A1 和 A2 中元素之和分别为 S1 和 S2。设计一个尽可能高效的划分算法，满足 |n1 - n2 最小且IS1 - S2| 最大。要求：
(1)给出算法的基本设计思想。
(2)根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
<!-- page 26 -->
(3)说明你所设计算法的平均时间复杂度和空间复杂度。
## 【2018年41题】
(13分）给定一个含n（n≥1）个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组{-5,3,2,3} 中未出现的最小正整数是1；数组{1,2,3}中未出现的最小正整数是4。要求：
(1)给出算法的基本设计思想。
(2)根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
(3)说明你所设计算法的时间复杂度和空间复杂度。
## 【2020年41题】
(13 分)定义三元组(a，b，c)（a，b，c 均为正数)的距离 D = la - bl + |b - cl + |c - a|。给定 3 个非空整数集合 S1、S2 和S3，按升序分别存储在3个数组中。请设计一个尽可能高效的算法，计算并输出所有可能的三元组(a，b，c)(a∈S1，b∈S2,c∈S3) 中的最小距离。例如 S1 = {-1, 0, 9}， S2 = {-25， -10, 10， 11}，S3 = {2, 9, 17， 30,41}，则最小距离为2，相应的三元组为(9，10，9)。要求：
(1)给出算法的基本设计思想。
(2)根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
(3)说明你所设计算法的时间复杂度和空间复杂度。
## 【2025年41题】
(13 分）有两个长度均为 n的一维整型数组 A[n]、res[n]，计算 A[i]与 A[i](0≤i≤i≤n-1)乘积的最大值，并将其保存到res[i] 中。若 A = {1, 4, -9, 6}，则得到 res[] = {6, 24, 81, 36}。现给定数组 A，请设计时间空间上尽可能高效的算法 王CalMulMax，求 res 中各元素的值。函数原型为：void CalMulMax(int A[], int res[], int n)。
(1)给出算法的基本思想。(4分)
(2)用C/C++ 描述算法关键之处给出注释。(7 分)
(3)说明时间、空间复杂度。(2分)
## 2.6 章节答案
## 2.6.1 习题
## \*习题2-1
(13 分）已知升序数组A 含有n 个整数，求是否存在值为 x的元素，存在返回数组下标，不存在则返回-1。设计一个在时间上尽可能高效的算法实现该功能。
例：A={1,2,3,7,8,11,15}，n = 7，x = 8，则返回数组下标为 4。
(1)给出算法的基本设计思想。
(2)根据设计思想，采用C、C++或Java语言描述算法，关键之处给出注释。
(3)说明你所设计算法的时间复杂度和空间复杂度。
<table><tr><td rowspan=1 colspan=1></td><td rowspan=1 colspan=1>做题思路</td><td rowspan=1 colspan=1>时间复杂度</td><td rowspan=1 colspan=1>空间复杂度</td><td rowspan=1 colspan=1>得分</td></tr><tr><td rowspan=1 colspan=1>暴力解</td><td rowspan=1 colspan=1>枚举</td><td rowspan=1 colspan=1>O(n)</td><td rowspan=1 colspan=1>0(1)</td><td rowspan=1 colspan=1>11</td></tr><tr><td rowspan=1 colspan=1>优化解</td><td rowspan=1 colspan=1>折半查找</td><td rowspan=1 colspan=1>O(logn)</td><td rowspan=1 colspan=1>0(1)</td><td rowspan=1 colspan=1>13</td></tr></table>
<!-- page 27 -->
## 【解法1】暴力解：枚举
(1)遍历一趟数组，依次判断每个元素是否为x，是则返回数组下标，如果遍历完还没找到则返回-1。
(2) 伪代码如下：
int ans(int A[], int n, int x)
{
for (int i=0; i<n; i++)
if (A[i]==x) return i;
return -1;
}
int B_Search(int A[], int L, int R, int x)
{
int mid;
while (L<=R)
{
mid=(L+R)/2; // mid 取中间数，向下取整
if (x==A[mid]) return mid; // 查找成功，返回数组下标 mid
if (x<A[mid]) R=mid-1; //取左一半
else L=mid+1; //取右一半
}
return -1; //查找失败 机考研 om
}
void Qsort(int A[], int L, int R)
{
if (L >= R) return; // 递归终止
int i = L, j = R, pivot = A[L];
while (i < j)
{
while (i < j && A[j] >= pivot) j--;
while (i < j && A[i] <= pivot) i++;
if (i < j) swap(A[i], A[j]);
}
swap(A[L], A[i]);
Qsort(A, L, i - 1);
Qsort(A, i + 1, R);
}
void ans(int A[], int n, int B[], int m)
{
int C[m + n];
for (int i = 0; i < n; i++) C[i] = A[i];
for (int i = 0; i < m; i++) C[n + i] = B[i];
Qsort(C, 0, m + n - 1);
// 输出数组 C
}
(3) // 时间复杂度： O((m + n)log(m + n)) 空间复杂度: O(log(m + n))
void Merge(int A[], int n, int B[], int m)
{
int C[m + n];
int i = 0, j = 0, k = 0;
while (i < n && j < m)
{
if (A[i] < B[j])
C[k++] = A[i++];
else
C[k++] = B[j++];
}
while (i < n) C[k++] = A[i++];
while (j < m) C[k++] = B[j++];
// 输出数组 C
}
3) // 时间复杂度：O(m + n) 空间复杂度: O(m + n)
int ans(int A[], int n)
{
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (A[i] == A[j]) return A[i];
return -1;
}
(3) // 时间复杂度：O(n²) 空间复杂度：O(1)
void Qsort(int A[], int L, int R)
{
if (L >= R) return;
int i = L, j = R, pivot = A[L];
while (i < j)
{
while (i < j && A[j] >= pivot) j--;
while (i < j && A[i] <= pivot) i++;
if (i < j) swap(A[i], A[j]);
}
swap(A[L], A[i]);
Qsort(A, L, i - 1);
Qsort(A, i + 1, R);
}
int ans(int A[], int n)
{
Qsort(A, 0, n - 1);
for (int i = 1; i < n; i++)
if (A[i] == A[i - 1]) return A[i];
return -1;
}
(3) // 时间复杂度：O(nlogn) 空间复杂度：O(logn)