内容导读
强化讲义 · 原始转写 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照
# 算法题讲义
<!-- page 1 -->
## 1 课程介绍
## 1.1 408 题型介绍
<table><tr><td rowspan=1 colspan=1></td><td rowspan=1 colspan=1>选择题 40 题</td><td rowspan=1 colspan=1>第41题</td><td rowspan=1 colspan=1>第42~47 题</td></tr><tr><td rowspan=1 colspan=1>分值</td><td rowspan=1 colspan=1>40×2</td><td rowspan=1 colspan=1>13~15分</td><td rowspan=1 colspan=1>55~57分</td></tr><tr><td rowspan=1 colspan=1>推荐时间</td><td rowspan=1 colspan=1>60~70 分钟</td><td rowspan=1 colspan=1>20 分钟</td><td rowspan=1 colspan=1>6×15 分钟</td></tr></table>
408考试时间非常紧张，很多同学反映题目做不完。算法大题往往是耗时最多的部分。因此，对于大多数同学而言，算法题的目标应该是“在尽可能短的时间内，拿到尽可能多的分数”。请牢记：时间就是分数！
## 1.2 本课程使用指南
本课程主要面向算法基础相对薄弱的同学，内容讲解细致，旨在帮助大家稳妥地拿下算法题的大部分分数。建议在学习完数据结构基础课后再开始本课程的学习。 L A
如果你是跨考或基础薄弱的同学：
1.先观看每一章的视频课程（包括直播和录播)，理解核心思想。
2. 独立完成配套的练习题，动手实践。
3.复看一遍本讲义，进行知识点的巩固和回顾。
如果你是基础较好的同学：
可以直接阅读讲义，快速掌握考点。
2.对有疑问或掌握不牢固的部分，再去观看对应的视频讲解。
部分带\*的小节表示可以跳过，部分带\*\*的小节表示仅供参考、意义不大、建议跳过。
## 焚诀
如果你觉得算法题拿70%的分数就挺好了，或者复习时间不够，可以如此学习：
<!-- page 2 -->
•第二、三、章可以只需要学习暴力解部分（直播的第1、2节课都可以先只学前半段)，树和图尽可能学习。
•“←”部分全部跳过。
## 1.3 审题
审题是算法题的灵魂。
一位一直不休息的考研前辈
审题是解对算法题的第一步，也是最重要的一步。一个条件的遗漏或误解，可能导致整个解题方向的错误。 V 城村
## 1.3.1 题目类型
考研算法题的考查范围通常集中在以下四种数据结构上，我们将在后续章节中逐一攻克：
第二章：顺序表（数组）
第三章：链表
第四章：树
第五章：图
第六章是一些必要的补充知识，大家可以当字典查阅。
## 1.3.2 复杂度要求
正确解读题目对时间/空间复杂度的要求，是写出符合标准答案的关键。考试中的复杂度一般指最坏时间/空间复杂度，只有当分析和快速排序有关的相关算法时使用平均复杂度
<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></tr><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></tr><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></tr><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></tr><tr><td rowspan=1 colspan=1>"空间复杂度为O(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>能实现即可</td><td rowspan=1 colspan=1>常见于树和图，重点考察逻辑实现</td></tr></table>
<!-- page 3 -->
## 对时间/空间复杂度有要求—顺序表、链表
这类题目通常存在多种解法（如暴力解、优化解)，需要我们给出最优解。
例：【2011年真题】（15分）一个长度为L（L≥1）的升序序列S，处在第「L/21个位置的数称为 S 的中位数。例如，若序列S1 = (11，13，15，17，19)，则 S1 的中位数是 15，两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2= (2, 4,6,8,20)，则S1 和S2 的中位数是11。现在有两个等长升序序列A和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数。分析：题目明确要求“时间和空间都高效”，暗示我们暴力解法（如合并数组后找中位数）虽然能做，但可能不是最优解。我们需要寻找更优的方法。
## 无复杂度要求——树、图
这类题目通常没有明确的复杂度限制，意味着解法比较固定，只要能正确实现逻辑即可，而不用考虑其他解法。
例：【2014年真题】（13分）二叉树的带权路径长度（WPL）是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T，采用二叉链表存储，结点结构如下
<table><tr><td>left</td><td>S weight</td><td>right</td></tr></table>
其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结点的指针，请设计求T的WPL的算法分析：题目没有提及任何复杂度要求，并且最后也没有要求分析复杂度。这强烈暗示我们，只需要通过遍历（如先序、后序或层序）等常规方法正确计算出WPL即可。
<!-- page 4 -->
## 1.3.3 挖掘易被忽略的信息
## 括号内的条件
出题人通常会把一些重要的条件放在括号内，这些条件可能会限制我们做这道题的方法，一定要划记下来。
例：【2025年真题】（13 分）有两个长度均为 n的一维整型数组 A[n]、res[n]，计算 A[i]与 A[i](0≤i≤j≤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)。 机
分析：该题最重要的条件就是(0≤i≤j≤n-1)，在考场上很多同学看到但忽视了这个条件，他们有一种惯性思维，碰到不会的顺序表的题就默认使用快速排序，但因为这个条件存在，我们不能随意改变数组A的分布，也就不能使用快速排序。
## 隐含的信息
除了明确文字，题目中还包含大量隐含信息，需要我们主动挖掘。
数据范围与特性：
"均为正整数"-> 无需考虑0 和负数。
"递增/有序"->暗示折半查找、双指针等高效算法。
"元素各不相同"-> 无需处理重复元素。
## 专业术语：
"稳定的排序"->不能使用快排、堆排、希尔排序。
"原地算法" -> 空间复杂度要求 O(1)。
"要求用递归/非递归"->直接限定了算法的实现结构。
<!-- page 5 -->
## 1.4 常见问题
## ？Q1：考试中能否使用 C++的 STL（标准模板库）？比如 sort()？
A：除了特别简单的数据结构（如栈、队列），其他一般情况下不允许。408考试的核心目的之一就是考察你对基础数据结构和算法的实现。使用STL会掩盖这些实现细节。你应该默认排序、折半查找等过程都需要自己手动实现。有一个简单的判断方法，如果这类不重要的数据结构或过程小于五行，那直接使用没问题，否则需要写清楚。常见可直接使用的部分大家可以阅读第六章。
## ？Q2：需要写 main 函数和 # include 头文件吗？
A：不需要。答题时只需要专注于实现题目要求的那个核心函数即可，评卷老师只看你的核心算法逻辑。 XY
## ？Q3：算法的“基本设计思想”应该怎么写？
A：用清晰、简洁的自然语言，分步骤描述你的算法逻辑。把它想象成你在向一个不懂编程的同学解释你的思路。例如：“1.定义两个指针i和j，分别指向两个数组的起始位置。2. 循环比较两个指针所指元素的大小...”。清晰的思路是高分代码的基础。
？Q4：如果想不出最优解，只写了暴力解法能得分吗？
A：能，而且推荐这样写！一个正确的暴力解法，通常能拿到该题一半以上的分数。这远比一个错误的优化解或直接放弃要好得多。在考场上，可以先写出暴力解确保基础分，然后在此基础上思考如何优化。 道
<!-- page 6 -->
## 2顺序表
我们从一道经典的真题开始本章的学习。
【2011年真题，15分】一个长度为L（L≥1）的升序序列S，处在第「L/21个位置的数称为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)说明你所设计
如何从暴力解法出发？(比如，将两个数组合并成一个大数组，再用快速排序找中位数)
如何利用“有序”这一特性进行优化？（比如，使用多指针法进行归并，或者更进一步，利用折半查找的思想)
如何在多种解法中权衡时间与空间复杂度？带着这些问题，让我们正式进入顺序表的世界，系统学习解决这类问题的通用方法和技巧。
## 2.1 思考流程
在面对顺序表（或链表）的算法题时，推荐大家遵循以下思考流程，稳扎稳打，确保得分。
推荐流程：构思暴力解 -> 思考能否优化 -> 构思优化解
暴力解法：最容易想到的、最直观的做法。通常思维难度小，但时间或空间复杂度较高，1难以拿到满分。
优化解法：在暴力解的基础上，利用题目给出的所有“隐藏”条件（如有序性、数据范围等)，降低算法的复杂度。通常思维难度较大，但得分会更高。
以一道15 分的算法大题为例，两种策略的投入产出比如下：
<table><tr><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>5分钟</td><td rowspan=1 colspan=1>11~12分</td></tr><tr><td rowspan=1 colspan=1>优化解法</td><td rowspan=1 colspan=1>10~20 分钟</td><td rowspan=1 colspan=1>13~15分</td></tr></table>
<!-- page 7 -->
原资料配图 · 转写内容请回源核验
直奔最优解
## 20分钟0分×
暴力后优化5分钟10分√
核心策略：先求暴力解，再求优化解。在考场上，孤注一掷地追求满分解法，如果失败可能导致一分不得。因此，无论如何，都应先确保能想出正确的暴力解法，拿到基础分，再尝试优化。 X\_
<!-- page 8 -->
## 2.2 暴力解法
练习：请在6分钟内想出以下例题的直观做法（不考虑复杂度）
例题2-1：已知升序数组 A含有 n 个整数，求是否存在值为x的元素，存在返回数组下标，不存在则返回-1。例：A={1，2,3，7，8，11，15}，n=7，x=8，则返回数组下标4。
例题2-2：已知两个整数升序数组 A 和 B，元素个数分别为 n 和 m，请将它们合并成一个新的升序数组 C。例：A={1，2，7}，B={3,4，5，10}，则C={1，2,3，4,5，7，10}。
例题2-3：已知数组 A 中有 n 个非负元素，每个元素值都小于 n，其中只有一个数重复出现过，请输出这个数。例：n=6，A={1，2，5，2，4，3}，则2重复出现，输出2。
例题 2-4：已知数组 A 含有 n 个整数 (n 为奇数)，求数组 A 的中位数。例：n=5，A={2，5, 9,3, 8}，排序后为 {2, 3,5, 8, 9}，中位数为 5。
例题2-5：已知数组 A 含有n 个整数，将小于 k的元素放在数组左侧，大于等于 k的元素放在右侧。例：n=7，A={4,5, 9,3,7,10，1}，k=6，处理后可能为 {1，3,4,5,9,7，10}。
例题 2-6：已知数组 A 含有 n 个整数，要求另一个数组 res，res[i] 表示长度为 i+1 的所有连续子序列中，元素和的最大值。
例：n=4，A={1,-2, 3, 5}，则res={5, 8, 6, 7}。
<table><tr><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>i=0</td><td rowspan=1 colspan=1>{1}、{-2}、{3}、{5}</td><td rowspan=1 colspan=1>{5}→5</td></tr><tr><td rowspan=1 colspan=1>i=1</td><td rowspan=1 colspan=1>{1, -2}、{-2, 3}、{3, 5}</td><td rowspan=1 colspan=1>{3, 5}→8</td></tr><tr><td rowspan=1 colspan=1>i=2</td><td rowspan=1 colspan=1>{1, -2, 3}、{-2, 3, 5}</td><td rowspan=1 colspan=1>{-2, 3, 5}→6</td></tr><tr><td rowspan=1 colspan=1>i=3</td><td rowspan=1 colspan=1>{1, -2, 3, 5}</td><td rowspan=1 colspan=1>{1, -2, 3, 5}→7</td></tr></table>
暴力解法，顾名思义，就是采用最直接、最不加思考优化的方法来解决问题。它不追求效率，只求能得到正确答案，因此常常是我们解题的“保底”方案或安全网。在顺序表的题目中，暴力解法通常体现为以下两种基本思想：枚举法和排序法。
## 2.2.1 枚举法
请大家回忆一下《复仇者联盟3》中，奇异博士在使用“超能力”看到14,000,605个不同的未来，发现只有1次可以赢。这种不辞辛劳、把所有可能性都尝试一遍来寻找答案的方法，就是我们今天要学习的一种最基础、也最花费时间的算法枚举法。为了找到问题的答案，枚举法要求我们系统地、一个不漏地尝试所有可能的解，直到找到正确的解，或者试完所有可能之后发现无解。
<!-- page 9 -->
原资料配图 · 转写内容请回源核验
我推进了时间浏览未来的可能性
去看即将到来的这一战所有可能出现的结果
一千四百万六百零五种
我们赢了几种
一种
枚举法，即“暴力穷举”，是解决问题时最简单、最直接的思路。它的核心思想朴素而强大：逐一考察所有可能的情况，然后从中找出满足题目条件的解。在实现上，考试中对应着一层或多层for循环。虽然“暴力”，但一个好的枚举算法也需要清晰的逻辑：
1. 确定枚举对象和范围：首先要明确我们要“枚举”的是什么？是数组中的一个元素、还是一个数对？然后确定其变化的范围，确保不漏掉任何一种可能，同时也要避免不必要的重复。
2. 进行条件判断：在枚举的过程中，对每一种可能的情况，根据题目的要求进行判断。如果符合条件，就执行相应的操作（如计数、更新最值或直接返回）。 城村
例题 2-1：对升序数组 A，求是否存在值为 x的元素，存在返回1，不存在返回-1。
暴力解：从头到尾遍历数组 A，逐个比较 A[i]与 x。
int findElement(int A[], int n, int x)
{
for (int i = 0; i < n; i++)
if (A[i] == x) return i; //命中
return -1; // 未找到，返回-1
}
//快速排序
{ void Qsort(int A[], int L, int R)
if (L >= R) return; // 区间≤1,返回
int i = L, j = R;
int pivot = A[L]; //选首元素为基准
// 不断交换左边比 pivot 大的数和右边比 pivot 小的数
while (i < j)
{
while (i < j && A[j] >= pivot) j--; // 从右找第—个 <pivot 的数
while (i j && A[i] <= pivot) i++; // 从左找第—个 >pivot 的数
if (i < j) swap(A[i], A[j]);
}
//将基准值A[L] 与A[i] 交换
swap(A[L], A[i]);
//递归处理左右两个子区间
Qsort(A, L, i - 1);
Qsort(A, i + 1, R);
}
//需要先默写上面的 Qsort 函数...
int findMedian(int A[], int n)
{
//调用快速排序
Qsort(A, 0, n - 1);
//对于奇数长度的数组，中位数下标是n/2
return A[n / 2];
}