1. 拿到题目先别急着写代码先搞清楚这题到底在考什么作为一个常年用 C 语言写单片机、后来又搞嵌入式 Linux 的工程师我对“第三大的数”这道题印象挺深。它经常出现在 C 语言练习题里翁恺老师的课后题里也有类似版本看起来人畜无害实际上能一口气写对的人真不多。题目本身很朴素给定一个整数数组返回数组中第三大的数如果不存在就返回最大的数。但是这个“第三大”的定义里藏着不少东西。这题适合谁来刷正在学 C 语言基础的学生、准备计算机二级或者软件设计师考试的人、还有想在面试前热热身找回手感的开发者都可以拿它当一块试金石。它考察的不是某个高深的数据结构而是你对数组遍历、去重、边界条件、整型溢出这些基本功的掌握程度。说白了这题是 C 语言基本功的“组合拳”循环、条件判断、变量维护、特殊值处理全在里面了。我在指导新人写这道题的时候最常看到的情况是一上来就写排序排序完直接取下标结果一看题目要求“第三大的数”不能包含重复值得先去重又得改。还有人把初始值设为 0结果数组里全是负数直接摆烂。所以这篇我就把这道题从需求拆解到多种实现、再到测试用例和调试技巧完整拆开讲一遍。不管你是刚学到数组这一章还是已经在刷题了照着这篇文章的思路走一遍绝对比你自己闷头写三小时收获大。1.1 题目越短坑越深三个隐藏条件必须提前定死“返回第三大的数”这句话之所以坑多是因为它没把游戏规则说透。第一数组里如果有重复元素比如[3, 2, 2, 1]第三大的数是多少按常理第三大应该是 1因为去重后的序列是3, 2, 1。但很多新手直接排序后取下标会得到 2这就错了。第二数组长度不足 3 个有效去重元素时怎么办比如[1, 2]只有两个不同的数题目说“不存在第三大就返回最大值”也就是返回 2。第三如果数组里的最大值刚好是INT_MIN也就是 -2147483648你怎么知道哪个变量是“初始值”哪个是“真实值”这三个条件不提前定死后面写什么都是空中楼阁。我的建议是打开编辑器之前先在注释里把规则写清楚——去重后的第三大、不存在返回最大、处理INT_MIN边界。规则定死了代码怎么写都不会跑偏。有人可能会问为什么题目不直接说清楚因为真实世界的需求文档比这还模糊。产品经理给你一句“找出第三大的数”你照样得去追问重复算不算不足三个怎么处理负数行不行这道题其实就是让你模拟一次真实的需求沟通场景所有边界条件都藏在不言中。1.2 方案选型三种主流思路的取舍分析面对“第三大的数”第一反应通常是排序。排完序之后从大到小扫一遍跳过重复值数到第三个就是答案。这个思路最直观C 标准库的qsort用起来也顺手缺点也很明显排序的时间复杂度是 O(n log n)如果数组只有 10 个元素无所谓但如果数组有 100 万个数排序就显得杀鸡用牛刀了。第二种思路是“三变量扫描法”也就是用三个变量分别记录当前遇到的最大值、第二大值、第三大值一趟遍历下来就能拿到结果时间复杂度是 O(n)空间复杂度是 O(1)。这个思路适合绝大多数场景也是我推荐的首选方案。它的难点不在于“理解”而在于“初始化”和“去重时的逻辑判断”。第三种思路是借助最小堆维护大小为 3 的堆来求第 K 大。这种思路适合“K 不固定”或者“数据是流式输入”的场景比如你一边接收数据一边想随时知道当前第三大是谁。但就这道题而言用堆有点小题大做C 语言手写堆的代码长度也劝退了不少新人。三种方案各有适用场景我的建议是初学者先把三变量法吃透再把排序法作为对比方案写一遍堆方案了解一下原理即可。等你把前两种写明白了这道题的价值已经赚到了。2. 核心实现一三变量扫描法一趟循环解决战斗三变量法的思路我习惯用“三个擂台”来类比一号擂台上站着最大的数二号擂台站着第二大的数三号擂台站着第三大的数。每来一个新选手数组里的数就和三个擂台的擂主比一比该往上顶就往上顶。比如新来的数比一号擂主还大那原来的一号擂主就被挤到二号擂台原来的二号擂主被挤到三号擂台原来的三号擂主直接淘汰。这个比喻很好懂但写代码的时候就会发现几个问题三个擂台一开始没人站初始值怎么定新选手和擂主打平值相等的时候要不要打架这几个问题不解决代码写出来就是漏洞百出。2.1 初始值的选择为什么不能直接赋 0我见过不少新手上来就写long max1 0, max2 0, max3 0;看这就埋雷了。如果数组里的数全是负数比如[-3, -2, -1, -4]正确答案应该是 -1。但三个变量初始值都是 0循环一圈下来0 一直赖在擂台上最后的结果就变成了“数组中不足三个不重复的数”时返回最大值——逻辑直接错乱。有人说那把三个变量初始化为INT_MIN不就完事了吗如果数组里真的包含INT_MIN这个数呢例如[INT_MIN, 1, 2, 3]去重后的排序是3, 2, 1, INT_MIN第三大是 1。如果用INT_MIN当初始值程序分不清变量里的INT_MIN到底是初始值还是真实值又会出错。我推荐的方案有两种。第一种是用一个布尔标志位数组记录“这个变量是否已经被赋值过”逻辑最清晰适合初学者。第二种是直接用LONG_MIN初始化因为题目给定的 int 范围下LONG_MIN永远不会出现在数组中可以安全地充当“哨兵值”。我平时喜欢用第二种代码简洁省掉一个标志位的判断。但需要说明的是LONG_MIN属于 long 范围变量类型得声明为long最后输出时注意格式控制符是%ld而不是%d。2.2 完整代码参考带注释的 C 语言实现下面是我推荐的实现变量命名尽量贴近语义注释也写得比较多方便直接照着理解#include stdio.h #include limits.h // 提供 INT_MIN/INT_MAX 等宏定义 int thirdMax(int* nums, int numsSize) { // 用 LONG_MIN 作为哨兵值确保数组中的任何 int 值都不会与它混淆 long max1 LONG_MIN; long max2 LONG_MIN; long max3 LONG_MIN; for (int i 0; i numsSize; i) { int num nums[i]; // 去重如果当前数已经存在三个擂台之一直接跳过 if (num max1 || num max2 || num max3) { continue; } // 比最大值还大顺位下移 if (num max1) { max3 max2; max2 max1; max1 num; } else if (num max2) { // 比最大值小但比第二大值大 max3 max2; max2 num; } else if (num max3) { // 比第二大值小但比第三大值大 max3 num; } } // 如果第三大依然还是哨兵值说明有效元素不足三个返回最大值 if (max3 LONG_MIN) { return (int)max1; } return (int)max3; }这段代码跑[3, 2, 1]会返回 1跑[2, 2, 3, 1]会返回 1跑[1, 2]会返回 2跑[1, 1, 1]会返回 1。光看逻辑可能不够直观建议你自己敲一遍代码然后在 main 函数里逐一测试。2.3 为什么要先判断去重再比大小你可能注意到了我在进入大小比较逻辑之前先做了一次“是否重复”的判断。这一步非常关键。假如去掉它数组[3, 3, 2, 1]会发生什么第一次遇到 3max3 变成 3第二次又遇到 3此时 3 比 max2 大max2 和 max1 被错误地更新成 3 和 3整个“三个不同值”的擂台就被污染了。正确的做法是任何一个元素如果它已经坐上了某个擂台后面再遇到一模一样的值直接忽略。这样做既保证了“第三大”的定义是“不同数值中的第三大”也顺带解决了重复元素导致结果偏差的问题。有同学可能会问如果数组里有重复的LONG_MIN呢前面说过原数组元素类型是 int而LONG_MIN比 int 最小值还小所以不会出现这种情况。这也是我坚持用LONG_MIN而不是INT_MIN的原因细节决定成败。3. 核心实现二排序法和计数法两种备选方案对比三变量法虽然是我推荐的主流方案但不是说其他方案一无是处。在实际项目里数据规模、数值范围、是否需要保留原始顺序等因素都会影响方案选型。这一节把排序法和计数法的思路、代码、适用场景都摆出来方便你做对比。3.1 排序法用 qsort 排序后从后往前去重排序法的思路很直白先从小到大排序然后从数组尾部最大值开始往前找不同的数找到第三个就是答案。C 语言里排序最方便的工具是标准库的qsort它接受一个比较函数用起来比手动写快排省心多了。比较函数长这样int cmp(const void* a, const void* b) { return (*(int*)a - *(int*)b); }注意一个问题如果两个整数相差非常大比如一个是INT_MAX一个是INT_MIN直接相减会溢出。稳妥一点的做法是用和比较后返回 1、-1、0int cmp(const void* a, const void* b) { int aa *(int*)a; int bb *(int*)b; if (aa bb) return 1; if (aa bb) return -1; return 0; }排序完成之后从最后一个元素开始用一个计数器记录遇到的不同值数量遇到新的不同值就加一加到 3 就返回当前值。如果数组遍历完了计数器还没到 3说明有效不同值不足 3 个返回最大值即可。排序法最大的优点是好理解、不容易写错缺点是 O(n log n) 的时间复杂度在大数据量下不划算。相同功能下三变量扫描法 O(n) 显然更优雅。不过在很多在线评测系统里这两种都能过毕竟数组规模一般限制在几万以内。3.2 计数法数值范围有限时的极致性能方案如果题目额外补充一句“数组元素的范围在 0 到 100 之间”那就完全不用排序和比较了直接用计数桶。开一个大小 101 的数组遍历原数组把每个数出现的次数累加到对应下标然后再从大到小扫计数桶数到第三个“出现次数大于 0”的下标就是答案。这个方案的复杂度是 O(n m)其中 m 是数值范围。它快得吓人但局限性也明显数值范围不能太大否则桶数组会爆炸数值为负时还得做偏移处理。所以它通常只在数值范围明确且有限的情况下使用属于“应对特化需求”的方案。从这道题本身来看我不推荐一上来就用计数法因为它绕远了。但如果后续你遇到类似“求最高频出现的前 K 个数”这类问题计数法的思想就会非常有用。先在这道题里打个底子不亏。4. 常见问题与排查技巧实录我踩过的坑都在这儿了这一节我打算把自己调试这类题目时遇到的典型问题、排查思路整理成一看就能用的经验。很多坑不是逻辑复杂而是细节太隐蔽一个疏忽就得 debug 半天。4.1 必测的六组测试用例写任何算法题先想清楚测试用例再动手写代码这个习惯越早养成越好。针对“第三大的数”我整理了一个亲测有效的测试用例表格你直接用就行输入数组预期结果备注[3, 2, 1]1最简单的正常场景[1, 2]2不足三个不同值返回最大值[2, 2, 3, 1]1重复值需要去重[1, 1, 1]1只有一个不同的值[-2147483648, 0, 1]-2147483648最小值作为真实值出现[5, 4, 4, 3]3中间值重复去重后依然是 3我特别要强调第五组那个带INT_MIN的用例。很多人在本地测试时不会想到这一层结果一交到在线评测系统就挂因为评测数据里偏偏就包含INT_MIN。写完代码之后把这六组数据全部跑一遍基本就能把隐藏得很深的边界问题全揪出来。4.2 我自己排查过的三个典型错误第一个错误是“返回值类型不匹配”。如果变量声明成long max1最后却用%d输出编译器可能只给你个警告但结果往往是错的。正确做法是全部用%ld输出或者在返回时强转回int。你要是拿不准就统一按long声明、%ld输出保证万无一失。第二个错误是“忘了处理去重”。这个问题在排序法里尤其常见排序完以为直接取倒数第三个下标就行了没考虑相同元素会连续出现。比如[3, 2, 2, 1]排序后是1, 2, 2, 3倒数第三个下标对应的是 1看起来对了但如果测试改成[3, 3, 2, 1]排序后是1, 2, 3, 3倒数第三个下标对应的是 2实际正确答案却是 1。所以排序法在取结果之前必须先做去重扫描。第三个错误是“初始化值污染结果”。我在前面反复提到INT_MIN的问题这里就不重复了。只想再提醒一句如果数组里真的存在和初始值相等的元素程序完全无法分辨“这是初始值”还是“这是真实值”。解决方案就是找一个数组永远不会出现、但又足够小的哨兵值LONG_MIN就是我的选择。4.3 调试小技巧printf 排查法在算法题里的妙用很多初学者一碰到运行结果不对就慌了满屏找逻辑漏洞。我的建议是用最原始也最有效的办法在关键位置加printf把循环里每个变量的变化过程打出来。比如在三变量法的循环里加上printf(num%d, max1%ld, max2%ld, max3%ld\n, num, max1, max2, max3);跑一组测试用例你一眼就能看出来是哪个分支判断出了问题是去重判断写错了还是赋值顺序颠倒了。调试通过之后把这行printf删掉或者注释掉就行。这个方法效率极高也比用调试器一步一步断点来得直观特别适合新手。5. 扩展思考从“第三大的数”到“第 K 大的数”刷题不能止步于 AC稍微往深想一层这道题的价值能翻好几倍。第三大的数是“第 K 大”这个通用问题的一个特例而“第 K 大”在生产环境里太常见了排行榜 TopK、系统日志 top 错误、电商热门商品排名全都属于这一类。5.1 泛化成第 K 大的思路快速选择与最小堆如果题目从“第三大”变成“第 K 大”三变量法立刻失效。这时候有两种主流解法第一种是快速选择算法QuickSelect本质是快排的二分思想平均时间复杂度 O(n)实现起来需要递归和分区操作代码复杂度比三变量高一个档次第二种是维护一个大小为 K 的最小堆遍历数组时如果元素比堆顶大就弹出堆顶并把新元素入堆堆里始终保留当前最大的 K 个元素堆顶就是答案。最小堆的时间复杂度是 O(n log K)在 K 很小的情况下性能非常可观。从这道题延伸出去你就摸到了“TopK 问题”的门槛。建议你把这段代码写完再把两种方案的复杂度分析写在注释里这个习惯对日后写项目、应付面试都很有用。5.2 结合文件读写从文件读取整数并求第三大的数有热词提到“C语言文件读写操作代码”我就顺手把这个场景也扩展一下。实际开发中你拿到的数据往往不在内存数组里而在一个文本文件里比如data.txt每行一个整数。你可以在本地生成几千个随机整数写进文件再写一段代码读取文件、计算第三大的数。核心步骤是用fopen打开文件while循环配合fscanf读取整数并依次更新三个变量读完关闭文件。这里有一个很关键的点文件可能为空所以读完一遍之后还要判断一下实际成功读取了多少个数字否则第三大的数会落在“未赋值”的初始值上。文件读写的流程代码骨架如下FILE* fp fopen(data.txt, r); if (fp NULL) { perror(无法打开文件); return 1; } long max1 LONG_MIN, max2 LONG_MIN, max3 LONG_MIN; int num; int count 0; while (fscanf(fp, %d, num) 1) { count; // 同样的去重 三变量比较逻辑 } fclose(fp);这段代码把纯算法题拉回到了真实应用场景也顺便练习了fopen、fscanf、fclose和文件指针判空这些基础操作。很多新手第一次接触文件读写时觉得烦其实就是因为没找到合适的应用载体。拿这道题当载体既练了算法又练了文件操作一举两得。5.3 内存管理视角为什么这道题不涉及动态分配既然热词里有“c语言内存管理”我就多嘴说一句这道题用固定数量的局部变量就能解决不需要动态内存分配这正是它适合初学者的原因之一。但如果你玩过链表、做过需要手动 malloc/free 的项目就会意识到 C 语言的“内存管理”往往是bug 重灾区。这道题虽然没有直接考察内存管理但它让我们看到算法设计得巧可以减少不必要的内存开销。三变量法之所以能保持空间复杂度 O(1)就是因为全程只用了三个 long 变量没有任何额外的数据结构。反过来看一段低级代码如下int temp[1000];如果数组元素个数未知盲目开大数组就是内存浪费开小了又可能越界。这些都是 C 语言程序员的日常挑战。建议你在刷完这道题之后专门花半小时研究一下malloc、free、calloc和指针之间的关系这一课迟早要用上。写在最后这道题留给我的后遗症老实说这道题让我养成了一个习惯写循环之前先习惯性地问自己三个问题——初始值会不会污染结果边界条件下的行为是什么重复值怎么处理这三个问题几乎适用于所有算法题甚至适用于真实的项目开发。我在实际工作中就用三变量法的思路处理过一段实时采集设备的 Top3 筛选逻辑每秒处理几千条数据如果真去排序性能根本扛不住但三变量扫描法一行循环就搞定了。算法不是纸面功夫它是真的能用到生产环境里的。如果你正被这道题折磨别慌这说明你正在经历一个正常的成长过程。照着文中的思路把三变量法写通、把六组测试用例跑通再回过头去把排序方案写一遍你的 C 语言基本功一定会扎实不少。最后再分享一个小技巧遇到任何数据结构或算法题先花三分钟在纸上写出伪代码再上编辑器。相信我这个习惯练好了你的代码速度和质量都能上一个台阶。