适用场景考研 408 数据结构——线性表与数组类算法设计题目标当最优算法暂时想不出来时先写出正确、完整、可执行的暴力算法稳定争取过程分。核心原则先保证正确再考虑优化。一、408 算法题中的“暴力解”到底是什么暴力解不是“随便写几个循环”而是按照题目要求枚举所有可能的候选判断候选是否合法计算候选对应的结果维护最终答案正确处理边界情况写明时间复杂度与空间复杂度。一个合格的暴力解应满足答案正确 枚举范围完整 不越界 能转化为 C/C 代码 复杂度分析正确在 408 算法设计题中即使没有写出标准最优算法只要暴力算法完整正确通常仍能获得设计思想、代码正确性和复杂度分析等过程分。二、考场上如何快速构造暴力解看到算法题时可以先问自己三个问题1. 题目要找的“答案对象”是什么一个元素一个下标一个数对一个三元组一个区间每个位置对应的一个结果。答案对象有几个自由变量通常就需要几层枚举。例如枚举一个元素 → 一层循环 枚举一个数对 → 两层循环 枚举一个三元组 → 三层循环2. 如何验证候选是否正确例如主元素统计候选值出现次数是否大于n/2最小未出现正整数扫描数组判断候选值是否出现最小距离三元组直接代入公式计算距离。3. 找到答案后如何处理常见处理方式第一个满足条件的候选立即返回求最小值不断更新min求最大值不断更新max为每个位置求答案每轮单独初始化并写入res[i]。三、经典题一寻找数组的主元素题目模型给定长度为n的整数数组A。若某个元素出现次数严格大于n/2则称其为主元素。若存在主元素输出该元素否则输出-1。暴力设计思想依次将数组中的每个元素A[i]作为候选主元素。对每个候选值从头到尾扫描数组统计它出现的次数。如果出现次数大于n/2则该元素就是主元素可以立即返回。若所有候选值都不满足条件则返回-1。其本质是枚举候选值 ↓ 统计候选值出现次数 ↓ 判断次数是否大于 n/2C 语言代码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都要重新初始化当前最值枚举本轮所有合法对象把结果写入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 算法题得分策略。
