适用场景：考研 408 数据结构——线性表与数组类算法设计题
目标：当最优算法暂时想不出来时，先写出正确、完整、可执行的暴力算法，稳定争取过程分。
核心原则：先保证正确，再考虑优化。

一、408 算法题中的“暴力解”到底是什么

暴力解不是“随便写几个循环”，而是按照题目要求：

1. 枚举所有可能的候选；

2. 判断候选是否合法；

3. 计算候选对应的结果；

4. 维护最终答案；

5. 正确处理边界情况；

6. 写明时间复杂度与空间复杂度。

一个合格的暴力解应满足：

答案正确 + 枚举范围完整 + 不越界 + 能转化为 C/C++ 代码 + 复杂度分析正确

在 408 算法设计题中，即使没有写出标准最优算法，只要暴力算法完整正确，通常仍能获得设计思想、代码正确性和复杂度分析等过程分。

二、考场上如何快速构造暴力解

看到算法题时，可以先问自己三个问题：

1. 题目要找的“答案对象”是什么

• 一个元素；

• 一个下标；

• 一个数对；

• 一个三元组；

• 一个区间；

• 每个位置对应的一个结果。

答案对象有几个自由变量，通常就需要几层枚举。

例如：

枚举一个元素 → 一层循环 枚举一个数对 → 两层循环 枚举一个三元组 → 三层循环

2. 如何验证候选是否正确

例如：

• 主元素：统计候选值出现次数是否大于n/2；

• 最小未出现正整数：扫描数组判断候选值是否出现；

• 最小距离三元组：直接代入公式计算距离。

3. 找到答案后如何处理

常见处理方式：

• 第一个满足条件的候选：立即返回；

• 求最小值：不断更新min；

• 求最大值：不断更新max；

• 为每个位置求答案：每轮单独初始化并写入res[i]。

三、经典题一：寻找数组的主元素

题目模型

给定长度为n的整数数组A。若某个元素出现次数严格大于n/2，则称其为主元素。若存在主元素，输出该元素；否则输出-1。

暴力设计思想

依次将数组中的每个元素A[i]作为候选主元素。

对每个候选值，从头到尾扫描数组，统计它出现的次数。如果出现次数大于n/2，则该元素就是主元素，可以立即返回。

若所有候选值都不满足条件，则返回-1。

其本质是：

枚举候选值 ↓ 统计候选值出现次数 ↓ 判断次数是否大于 n/2

C 语言代码

int findMajority(int A[], int n) { int i, j, count; for (i = 0; i < n; i++) { count = 0; for (j = 0; j < n; j++) { if (A[j] == A[i]) { count++; } } if (count > n / 2) { return A[i]; } } return -1; }

复杂度分析

外层循环最多执行n次，每次内层扫描整个数组：

时间复杂度：O(n²) 空间复杂度：O(1)

考试易错点

错误 1：写成count >= n / 2

主元素要求出现次数严格大于一半，因此应写：

count > n / 2

错误 2：找到候选值后没有重新计数

每次更换候选值时，count必须重新置为0。

错误 3：只找到“候选值”，没有验证

主元素题中，得到候选值不等于已经证明它是主元素。必须统计其出现次数。

四、经典题二：寻找未出现的最小正整数

题目模型

给定一个含n个整数的数组，找出数组中未出现的最小正整数。

例如：

A = {-5, 3, 2, 3}

未出现的最小正整数为1。

若：

A = {1, 2, 3}

答案为4。

暴力设计思想

从正整数1开始依次枚举候选值。

对于每个候选值i，扫描整个数组，判断数组中是否存在等于i的元素：

• 若存在，则继续检查i + 1；

• 若不存在，则i就是最小未出现正整数，立即返回。

长度为n的数组中，答案一定在：

1 到 n + 1

因此只需检查1到n。若它们全部出现，则返回n + 1。

C 语言代码

int findMissMin(int A[], int n) { int i, j; int found; for (i = 1; i <= n; i++) { found = 0; for (j = 0; j < n; j++) { if (A[j] == i) { found = 1; break; } } if (found == 0) { return i; } } return n + 1; }

复杂度分析

最坏情况下，需要对每个候选值都扫描整个数组：

时间复杂度：O(n²) 空间复杂度：O(1)

为什么答案不会超过n + 1

数组中只有n个元素。

即使数组中正好包含：

1, 2, 3, ..., n

此时最小未出现正整数也只是：

n + 1

所以答案必然落在：

[1, n + 1]

考试易错点

错误 1：只检查到n，没有写兜底返回值

如果1到n全部出现，答案是：

return n + 1;

错误 2：找到候选值后仍继续扫描

发现候选值已出现后，可以立即break，避免无效比较。

错误 3：从0开始枚举

题目要求的是正整数，因此必须从1开始。

五、经典题三：三个升序集合的最小距离

题目模型

定义三元组(a, b, c)的距离为：

D = |a - b| + |b - c| + |c - a|

其中：

a ∈ S1 b ∈ S2 c ∈ S3

要求找出所有合法三元组中的最小距离。

暴力设计思想

分别从三个集合中各选一个元素，组成所有可能的三元组。

使用三层循环：

第一层：枚举 S1 中的元素 a 第二层：枚举 S2 中的元素 b 第三层：枚举 S3 中的元素 c

对每个三元组计算距离，并不断更新当前最小值。

C 语言代码

#include <stdlib.h> int minDistance(int S1[], int n1, int S2[], int n2, int S3[], int n3) { int i, j, k; int d; int minD = abs(S1[0] - S2[0]) + abs(S2[0] - S3[0]) + abs(S3[0] - S1[0]); for (i = 0; i < n1; i++) { for (j = 0; j < n2; j++) { for (k = 0; k < n3; k++) { d = abs(S1[i] - S2[j]) + abs(S2[j] - S3[k]) + abs(S3[k] - S1[i]); if (d < minD) { minD = d; } } } } return minD; }

复杂度分析

三个集合长度分别为n1、n2、n3：

时间复杂度：O(n1 × n2 × n3) 空间复杂度：O(1)

若三个集合长度都记为n：

时间复杂度：O(n³)

考试易错点

错误 1：三层循环的集合写混

必须保证：

S1[i] S2[j] S3[k]

分别对应三个集合。

错误 2：最小值初始化为0

距离非负，如果把最小值初始化为0，后续所有距离都不可能更小，结果会永远错误。

正确做法是用第一个合法三元组初始化：

minD = 第一个三元组的距离;

错误 3：只计算距离，没有维护最小值

暴力枚举只是第一步。必须通过：

if (d < minD) minD = d;

维护最终答案。

六、408 算法设计题的统一答题模板

考试时建议严格按照下面三个部分作答。

1. 基本设计思想

不要只写“使用暴力法”，而要说明：

• 枚举什么；

• 如何判断；

• 何时更新；

• 最后返回什么。

通用模板：

依次枚举所有可能的候选解。对于每个候选解，按照题目条件进行验证或计算， 若其满足要求，则更新当前答案。枚举结束后输出最终结果。

2. 算法代码

代码至少应保证：

• 循环范围正确；

• 数组下标不越界；

• 变量初始化正确；

• 返回值完整；

• 所有分支都能推进；

• 不出现死循环。

3. 复杂度分析

复杂度不能只看“有几个 for”，而要看循环之间的关系。

嵌套执行

for (...) for (...)

时间复杂度通常相乘：

O(n) × O(n) = O(n²)

顺序执行

for (...) for (...)

时间复杂度相加：

O(n) + O(n) = O(n)

不等长数组

不要一律写成O(n²)或O(n³)。

例如三集合枚举应写：

O(n1 × n2 × n3)

七、408 暴力解的高频失分点

1. 最大值或最小值初始化错误

求最大值时，不要默认初始化为0，因为结果可能是负数。

更稳妥的写法：

maxValue = 第一个合法结果;

求最小值同理。

2. 漏掉循环正常结束后的返回值

很多算法存在两个出口：

中途找到答案 → 立即返回 所有候选都检查完 → 返回兜底答案

例如最小未出现正整数：

return n + 1;

3. 没有区分“一个总答案”和“每个位置一个答案”

如果题目要求得到res[i]，则每个i都要：

1. 重新初始化当前最值；

2. 枚举本轮所有合法对象；

3. 把结果写入res[i]。

不能只维护一个全局最大值。

4. 能边枚举边更新，却额外开数组

例如求最大乘积时，可以直接：

if (product > maxValue) maxValue = product;

没有必要先把所有乘积存入辅助数组，再重新扫描。

原则：

只需要最值时，优先边枚举边更新。

5. 题目条件没有用全

算法题中的每个条件都可能影响循环范围和边界判断，例如：

• 等长；

• 升序；

• 非空；

• 元素范围；

• i ≤ j；

• 只要求前若干个元素。

先圈出条件，再写代码。

八、如何用暴力解争取 408 算法题过程分

当最优算法想不出来时，建议按以下顺序写：

第一步：先写正确的基本思想

即使代码没完全写完，正确的枚举思路也有机会获得设计思想分。

第二步：把循环范围写清楚

例如：

for (i = 0; i < n; i++) for (j = i; j < n; j++)

循环边界往往是评分点。

第三步：写出关键更新语句

例如：

count++; minD = d; res[i] = maxValue;

第四步：补上边界和返回值

重点检查：

空数组是否允许 数组是否越界 循环结束后返回什么 相等情况如何处理 负数是否影响初始化

第五步：复杂度必须写

即使算法不够优，也要准确写出：

时间复杂度 空间复杂度

不要为了显得高效而虚报复杂度。

九、考场检查清单

交卷前，快速检查以下内容：

• 我枚举了所有合法候选吗？

• 有没有漏掉最后一种情况？

• 数组下标会不会越界？

• 最大值或最小值初始化合理吗？

• 相等情况是否处理？

• 找到答案后是否应该立即返回或break？

• 循环结束后是否有兜底返回值？

• 复杂度是相加还是相乘？

• 题目要求一个答案，还是res[]中多个答案？

• 代码是否真正实现了设计思想？

十、总结

408 算法题中，暴力解的核心不是“循环多”，而是：

枚举完整 判断正确 边界清楚 代码可执行 复杂度准确

最稳定的思考链是：

题目要找什么 ↓ 答案由几个变量决定 ↓ 用几层循环枚举 ↓ 如何验证或计算 ↓ 如何维护最终答案 ↓ 检查边界与复杂度

在考场上，最优算法暂时想不出来并不可怕。真正危险的是空着不写，或者只写一句模糊的“遍历数组”。

先写出正确的暴力方案，再在时间允许时优化，是更稳妥的 408 算法题得分策略。