说在前面

部分题目只是思想相同，并非完全一样的题目，比如2010年的题目和力扣的题目，做题时请注意。不同的题目我会标注。
如果你要使用C++写题目，请不要使用Vector，String等STL容器。否则，考试中将不能得分。
简单的函数，如math类等，可以酌情使用，使用后请用注释解释含义。
想看原题，可前往此网站：408题库↗
暴力解只会扣2-3分，所以想不到好方法，可以直接暴力。

顺序表的应用

2010年

设将 $n\ (n>1)$ 个整数存放到一维数组 $R$ 中。试设计一个在时间和空间两方面都尽可能高效的算法。将 $R$ 中保存的序列循环左移 $p\ (0<p<N)$ 个位置，即将 $R$ 中的数据由 $<x_0, x_1, \cdots, x_{n-1}>$ 变换为 $<x_p, x_{p+1}, \cdots, x_{n-1}, x_0, x_1, \cdots, x_{p-1}>$ 。要求：

给出算法的基本设计思想。
根据设计思想，采用 C 或 C++ 语言描述，关键之处给出注释。
说明你所设计算法的时间复杂度和空间复杂度。

https://leetcode.cn/problems/rotate-array/description/↗ 【diff:向左、向右】

2011年

一个长度为 $L$ （ $L \geq 1$ ）的升序序列 $S$ ，处在第 $\lceil L/2 \rceil$ 个位置的数称为 $S$ 的中位数。例如，若序列 $S_1 = (11,13,15,17,19)$ ，则 $S_1$ 的中位数是 15。两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若序列 $S_2 = (2,4,6,8,20)$ ，则 $S_1$ 和 $S_2$ 的中位数是 11。现有两个等长的升序序列 $A$ 和 $B$ ，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列 $A$ 和 $B$ 的中位数。要求：

给出算法的基本设计思想。
根据设计思想，采用 C 或 C++ 语言描述，关键之处给出注释。
说明你所设计算法的时间复杂度和空间复杂度。

https://www.acwing.com/problem/content/3822/↗

2013年

已知一个整数序列 $A = (a_0, a_1, \dots, a_{n-1})$ ，其中 $0 \le a_i < n \ (0 \le i < n)$ 。若存在 $a_{p_1} = a_{p_2} = \dots = a_{p_m} = x$ 且 $m > n/2 \ (0 \le p_k < n, 1 \le k \le 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$ 。要求：

给出算法的基本设计思想。
根据设计思想，采用 C、C++ 语言描述算法，关键之处给出注释。
说明你所设计算法的时间复杂度和空间复杂度。

https://leetcode.cn/problems/majority-element/description/↗ 【diff：无需判空、元素无限制范围】

2018年

给定一个含 $n(n \ge 1)$ 个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组 $\{-5, 3, 2, 3\}$ 中未出现的最小正整数是 1；数组 $\{1, 2, 3\}$ 中未出现的最小正整数是 4。要求：

给出算法的基本设计思想。
根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。
说明你所设计算法的时间复杂度和空间复杂度。

https://leetcode.cn/problems/first-missing-positive/description/↗ 【diff：要求常数级别额外空间】

https://www.acwing.com/problem/content/3823/↗

2020年

定义三元组 $(a,b,c)$ （ $a,b,c$ 均为正数）的距离 $D = |a-b| + |b-c| + |c-a|$ 。给定 3 个非空整数集合 $S_1,S_2,S_3$ ，按升序分别存储在 3 个数组中。请设计一个尽可能高效的算法，计算并输出所有可能的三元组 $(a,b,c)$ （ $a \in S_1, b \in S_2, c \in S_3$ ）中的最小距离。例如 $S_1 = \{-1, 0, 9\}, S_2 = \{-25, -10, 10, 11\}, S_3 = \{2, 9, 17, 30, 41\}$ 。则最小距离为 2，相应的三元组为 $(9,10,9)$ 。

要求：

给出算法的基本设计思想；
根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释；
说明你所设计算法的时间复杂度和空间复杂度。

https://www.acwing.com/problem/content/3877/↗

2025年

设有两个长度均为 $n$ 的一维整型数组 $A$ 和 res，对数组 $A$ 中的每个元素 $A[i]$ ，计算 $A[i]$ 与 $A[j]$ （ $0 \le i \le j \le 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)

要求:

给出算法的基本设计思想：
根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释：
说明你所设计算法的时间复杂度和空间复杂度。

Thanks for reading!

408算法题汇总

周六 9月 26 2026

1212 字 · 5 分钟

考研 408

408算法题汇总

说在前面

顺序表的应用

2010年

2011年

2013年

2018年

2020年

2025年

408算法题汇总

Comments

⎋ⁱ̴̴̴≮̸̸̴⨦̷̶̷⟁̶░̴̷.̵̐͝⟆⟟ⷙ̶̸⚚⍜⛀⍦꙰