🏷️ 知识点：顺序表
下列对顺序存储的有序表（长度为 n）实现给定操作的算法中平均时间复杂度为 O(1) 的是（ ）。
A. 查找包含指定值元素的算法 B. 插入包含指定值元素的算法 C. 删除第 i 个元素的算法 D. 获取第 i 个值的算法
[tag_link]
正确答案：D
线性表的顺序存储结构采用一组地址连续的存储单元依次存储线性表的数据元素。特点是逻辑上相邻的数据元素在物理位置上相邻。线性表顺序存储结构是一种随机存取的存储结构，设线性表的每个元素占 L 个存储单元，第一个元素a1的存储地址是 LOC(a1)，则任意元素ai的 LOC(ai)=LOC(a1)+(i-1)*L。因此获取第 i 个值的算法为常量阶 O(1)。
已知一个整数序列A=(a0,a1,…,an−1)，其中0≤ai<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) 说明你所设计算法的时间复杂度和空间复杂度。
1）给出算法的基本设计思想：算法的策略是从前向后扫描数组元素，标记出一个可能成为主元素的元素 Num。然后重新计数，确认 Num 是否为主元素。算法可分为以下两步：① 选取候选的主元素：依次扫描所给数组中的每个整数，将第一个遇到的整数 Num 保存到 c 中，记录 Num 的出现次数为 1；若遇到的下一个整数仍等于 Num，则计数加 1，否则计数减 1；当计数减到 0 时，将遇到的下一个整数保存到 c 中，计数重新记为 1，开始新一轮计数，即从当前位置开始重复上述过程，直到扫描完全部数组元素。② 判断 c 中元素是否是真正的主元素：再次扫描该数组，统计 c 中元素出现的次数，若大于 2，则为主元素；否则，序列中不存在主元素。
2）算法实现
int majority(int a[], int n) {
if (n == 0) {
return -1;
}
// 选取候选元素
int num = a[0];
int cnt = 1;
// 如果主元素存在，会被以下过程筛选出来
// 但是筛选出来的不一定是主元素
for (int i = 1; i < n; i++) {
if (a[i] == num) {
// 候选元素个数 +1
cnt++;
} else {
// 重新设置候选元素
cnt--;
if (cnt == 0) {
num = a[i];
cnt = 1;
}
}
}
// 再判断候选元素是不是主元素
int m = 0;
for (int i = 0; i < n; i++) {
// 统计候选元素出现的次数
if (a[i] == num) {
m++;
}
}
if (m > n / 2) {
return num;
}
return -1;
}
【评分说明】① 若考生设计的算法满足题目的功能要求且正确，则 (1)、(2) 根据所实现算法的效率给分，细则见下表：
| 时间复杂度 | 空间复杂度 | (1) 得分 | (2) 得分 |
|---|---|---|---|
| O(n) | O(1) | 4 | 7 |
| O(n) | O(n) | 4 | 6 |
| O(nlog₂n) | 其他 | 3 | 6 |
| ≥O(n²) | 其他 | 3 | 5 |
② 若在算法的基本设计思想描述中因文字表达没有非常清晰反映出算法思路，但在算法实现中能够清晰看出算法思想且正确的，可参照①的标准给分。③ 若算法的基本设计思想描述或算法实现中部分正确，可参照①中各种情况的相应给分标准酌情给分。
(3) 说明算法复杂性：参考答案中实现的程序的时间复杂度为O(m)，空间复杂度为O(1)。【评分说明】若考生所估计的时间复杂度与空间复杂度与考生所实现的算法一致，可各给 1 分。【说明】本题如果采用先排好序再统计的方法，只要解答正确，最高可拿 9 分，因此对于统考算法题，去花费大量时间去思考最优解法是得不偿失的。
给定一个含 n(n≥1) 个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组{-5, 3, 2, 3}中未出现的最小正整数是 1；数组{1, 2, 3}中未出现的最小正整数是 4。要求：
(1) 给出算法的基本设计思想。
(2) 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。
(3) 说明你所设计算法的时间复杂度和空间复杂度。
[tag_link]
1）题目要求算法时间上尽可能高效，因此采用空间换时间的办法。分配一个用于标记的数组B[n]，用来记录A中是否出现了1∼n中的正整数，B[0]对应正整数1，B[n−1]对应正整数n，初始化B中全部为0。由于A中含有n个整数，因此可能返回的值是1∼n+1，当A中n个数恰好为1∼n时返回n+1。当数组A中出现了小于等于0或大于n的值时，会导致1∼n中出现空余位置，返回结果必然在1∼n中，因此对于A中出现了小于等于0或大于n的值可以不采取任何操作。经过以上分析可以得出算法流程：从A[0]开始遍历A，若0<A[i]≤n，则令B[A[i]−1]=1；否则不进行操作。对A遍历结束后，开始遍历数组B，若能查找到第一个满足B[i]=0的下标i，返回i+1即为结果，此时说明A中未出现的最小正整数在1∼n之间。若B[i]全部不为0，返回i+1（跳出循环时i=n，i+1等于n+1），此时说明A中未出现的最小正整数是n+1。
2）算法实现
int findMissMin(int a[], int n) {
// 来记录 1 ~ n 是否出现过
int vis[n];
for (int i = 0; i < n; i++) {
vis[i] = 0;
}
// 在 vis 数组中记录哪些正整数出现过
for (int i = 0; i < n; i++) {
int num = a[i];
if (num > 0) {
vis[num-1] = 1;
}
}
// 遍历 vis 来找到最小消失的正整数
for (int i = 0; i < n; i++) {
if (vis[i] == 0) {
return i+1;
}
}
return n+1;
}
3）时间复杂度：遍历A一次，遍历B一次，两次循环内操作步骤为O(1)量级，因此时间复杂度为O(n)。空间复杂度：额外分配了B[n], 空间复杂度为O(n)。
定义三元组(a,b,c)（a,b,c均为正数）的距离D=∣a−b∣+∣b−c∣+∣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）说明你所设计算法的时间复杂度和空间复杂度
[tag_link]
分析，由D=∣a−b∣+∣b−c∣+∣c−a∣≥0得：① 当a=b=c时，距离最小。② 其余情况。不失一般性，假设观察下面的数轴：
L1 =∣a−b∣，L2 =∣b−c∣，L3 =∣c−a∣，D=∣a−b∣+∣b−c∣+∣c−a∣=L1 +L2 +L3 =2L3由D的表达式可知，事实上决定D大小的关键是a和c之间的距离，于是问题就可以简化为每次固定c找一个a使得L3 =∣c−a∣最小。
1）算法的基本设计思想
- 使用Dmin记录所有已处理过的三元组的最小距离，初值为一个足够大的整数。
- 集合S1、S2和S3，分别保存在数组A、B、C中。数组的下标变量i=j=k=0，当i<S1、j<S2且k<S3时（∣S∣表示集合S中的元素个数），循环执行以下过程：
- 计算（A[i]，B[j]，C[j]）的距离D；（计算D）
- 若D<Dmin，则Dmin =D；（更新D)
- 将A[i]，B[i]，C[j]中的最小值的下标+1；（对照分析：最小值为a，最大值为c，这里c不变而更新a，试图寻找更小距离D）
- 输出Dmin，结束。
2）算法实现
void solve(int S1[], int n1, int S2[], int n2, int S3[], int n3) {
int i = 0, j = 0, k = 0;
int res = INT32_MAX;
while (i < n1 && j < n2 && k < n3) {
int a = S1[i], b = S2[j], c = S3[k];
int D = abs(a-b) + abs(b-c) + abs(a-c);
res = min(res, D);
int v = min3(a, b, c);
if (v == a) {
i++;
} else if (v == b) {
j++;
} else {
k++;
}
}
return res;
}
3）设n=∣S1 ∣+∣S2 ∣+∣S3 ∣，时间复杂度为O(n)，空间复杂度为O(1)。
设有两个长度均为 n 的一维整型数组 A 和 res，对数组 A 中的每个元素 A[i]，计算 A[i] 与 A[j](0 ≤ i ≤ j ≤ n-1) 乘积的最大值，并将其保存到 res[i]中。例如，若 A[i] = {1, 4, -9, 6}，则得到 res[i] = {6, 24, 81, 36}。现给定数组 A，请设计一个时间和空间上尽可能高效的算法 calMulMax，求 res 中各元素的值。函数原型为：void calMulMax(int A[], int res[], int n)，要求：
(1) 给出算法的基本设计思想：（4 分）
(2) 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释：（7 分）
(3) 说明你所设计算法的时间复杂度和空间复杂度。（2 分）
[tag_link]
1）若 A[i] 为负数的话，则 A[j] 为子数组 A[i:n] 中的最小值时，A[i] * A[j] 为最大值。若 A[i] 为正数的话，则 A[j] 为子数组 A[i:n] 中的最大值时，A[i] * A[j] 为最大值。因此算法步骤如下：
- 从右到左遍历数组
A：
- 维护一个变量
maxValue来存储当前从i到n-1范围内的最大值。 - 维护一个变量
minValue来存储当前从i到n-1范围内的最小值。 - 在每次迭代中，更新
maxValue和minValue。 - 计算
A[i] * maxValue和A[i] * minValue，并将它们的较大值存储在res[i]中。
- 更新
maxValue和minValue：在每次迭代中，maxValue是当前元素与之前的maxValue的较大值，minValue是当前元素与之前的minValue的较小值。
2）算法实现如下：
void calMulMax(int A[], int res[], int n) {
int minValue = INT32_MAX;
int maxValue = INT32_MIN;
for (int i = n-1; i >= 0; i--) {
if (A[i] < minValue) {
minValue = A[i];
}
if (A[i] > maxValue) {
maxValue = A[i];
}
if (A[i] > 0) {
res[i] = A[i] * maxValue;
} else {
res[i] = A[i] * minValue;
}
}
}
3）算法的时间复杂度为 O(n)，空间复杂度为 O(1)。
设将n(n>1) 个整数存放到一维数组 R 中。试设计一个在时间和空间两方面都尽可能高效的算法。将 R 中保存的序列循环左移p(0<p<N) 个位置，即将 R 中的数据由<x0,x1,⋯,xn−1>变换为<xp,xp+1,⋯,xn−1,x0,x1,⋯,xp−1>。要求：
(1) 给出算法的基本设计思想。
(2) 根据设计思想，采用 C 或 C++ 或 Java 语言描述，关键之处给出注释。
(3) 说明你所设计算法的时间复杂度和空间复杂度。
[tag_link]
1）算法的基本设计思想可以将这个问题视为把数组ab转换成数组ba（a代表数组的前p个元素，b代表数组中余下的n−p个元素），先将a逆置得到a−1b, 再将b逆置得到a−1b−1，最后将整个a−1b−1逆置得到(a−1b−1)−1=ba。设 Reverse 函数执行将数组元素逆置的操作，对 abcdefgh 向左循环移动 3(p=3) 个位置的过程如下：Reverse(0,p-1) 得到 cbadefgh:Reverse(p,n-l) 得到 cbahgfed;Reverse(0,n-l) 得到 defghabc,注：Reverse 中，两个参数分别表示数组中待转换元素的始末位置。
2）使用 C 语言描述算法如下：
void reverse(int a[], int from, int to) {
int i = from;
int j = to;
while (i < j) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
i++;
j--;
}
}
void loopMove(int a[], int n, int p) {
if (p < 0) {
return;
}
p = p % n;
reverse(a, 0, p-1);
reverse(a, p, n-1);
reverse(a, 0, n-1);
}
3）上述算法中 3 个 Reverse 函数的时间复杂度分别为O(p/2)、O((n−p)/2)和O(n/2)，故所设计的算法的时间复杂度为O(n)，空间复杂度为O(1)。【另解】借助辅助数组来实现。算法思想：创建大小为p的辅助数组S，将R中前p个整数依次暂存在S中，同时将R中后p个整数左移，然后将S中暂存的p个数依次放回到R中的后续单元。时间复杂度为O(n), 空间复杂度为O(p)。