“第三大的数”这道题估计不少C语言学习者都刷到过尤其是跟着翁恺老师的课程一路走下来的同学。题干就一句话给定一个整数数组返回数组中第三大的数如果不存在就返回最大的那个数。很多人口算三秒钟就动手觉得无非是排序取倒数第三个结果改了一晚上提交还是不通过。我当年第一次做这道题也交了三回才过。这道题真正让人难受的地方在于它考的并不是排序或者遍历而是你怎么处理“第三大”这三个字里藏着的各种隐藏细节。这篇就把它的考点、两种主流写法还有我踩过的坑一起说清楚。1. 题目拆解看起来简单坑全藏在“第三大”三个字里1.1 这道题到底在考什么很多人第一眼看到“第三大的数”立刻想到排序然后把数组排完序取倒数第三个元素完事。这个思路放在数学题里没问题放到编程题里就会踩坑因为题目里“第三大”的定义和日常口语不完全一样。第一它要求的是“不同值”的第三大。比如数组是[1, 2, 2, 3]去重之后是{1, 2, 3}第三大是 1。如果你直接按下标取倒数第三个位置得到的是 2这就是错的。第二如果去重之后不足三个数要返回最大值。比如[1, 2]没有第三大的数题目要求返回最大的那个数也就是 2。再比如[5, 5, 5]去重之后只有一个数 5那第三大就是 5。第三数组里可能包含负数也可能包含INT_MIN这个特殊值。这一点看起来不起眼却是很多人用哨兵初始化时翻车的根源。所以这道题表面上在考数组遍历、排序、条件判断实际上在考三件事去重逻辑、边界条件处理、以及哨兵值的安全设计。这三件事恰恰是C语言基本功里最容易忽略的地方。1.2 三处隐藏规则逐条拆开揉碎先说去重。排序之后相同的数字会排在一起所以去重的写法一般是从后往前遍历遇到和前一个元素不同的值就计一个数。这里的计数顺序是从大到小所以第一个遇到的不同值就是最大值第二个是第二大第三个就是我们要的第三大。如果整个数组遍历完了还没数到三个不同值就说明数组中不同值的个数不足三个那直接返回最大值nums[numsSize-1]即可。再说边界条件。数组长度可能是 1、2也可能是几千上万。排序法里如果数组只有 1 个元素那么倒数第二个位置的下标是 -1直接访问会越界。所以不能用“固定取倒数第三个位置”这种写法必须用计数器去数数满三个才返回。最后说哨兵值。这是整个题目最阴险的地方。很多初学者会用INT_MIN来初始化三个变量分别表示第一大、第二大、第三大。但INT_MIN本身是int类型能表示的最小值如果数组里正好有一个元素的值等于INT_MIN那程序就无法区分“这个变量还没有被赋值”和“这个变量已经被赋值为INT_MIN”于是判断结果就会出错。这个问题在第 3 章会详细展开。2. 解法一排序后去重定位先保证做对再说优化2.1 实现步骤梳理排序法是最容易想到的方案也是最适合用来验算思路的方案。整个流程分三步第一步调用qsort把数组从小到大排序。注意C语言里qsort需要自己写比较函数这个函数写不好后面全白搭。第二步从数组末尾往前遍历。因为排序后数组是从小到大所以末尾是最大值。拿每个元素和前一个比较如果不同说明遇到了一个新的“档位”计数器加一。当计数器等于 3说明已经遇到了第三大的不同值直接返回当前元素。第三步如果循环走完计数器都没到 3说明不同值总数不超过 2 个那就返回数组末尾的最大值。这套写法的时间复杂度是O(n log n)主要来自排序。对于力扣 414 这种数据规模完全够用。它最大的价值是“逻辑简单、不容易藏 bug”适合作为第一版提交。2.2 完整代码示例与关键说明#include stdio.h #include stdlib.h int cmp_int(const void *a, const void *b) { int x *(const int *)a; int y *(const int *)b; return (x y) - (x y); } int thirdMax(int *nums, int numsSize) { qsort(nums, numsSize, sizeof(int), cmp_int); int distinctCount 1; for (int i numsSize - 2; i 0; i--) { if (nums[i] ! nums[i 1]) { distinctCount; if (distinctCount 3) { return nums[i]; } } } return nums[numsSize - 1]; }这里有两个细节需要说明。第一个是比较函数cmp_int我用了(x y) - (x y)这种写法而不是传统的return x - y。为什么因为如果x是INT_MAXy是INT_MINx - y会超出int范围导致未定义行为。虽然很多测试数据碰不上这种事但养成写安全比较函数的习惯没有坏处。第二个细节是循环起始下标numsSize - 2。因为我们要和“前一个元素”比较所以从倒数第二个位置开始逐个往前扫。如果有人写成for (int i numsSize - 3; i 0; i--)那就忽略了去重过程本身也需要统计最大值和第二大值的情况容易出现遗漏。2.3 这种方案的短板排序法的缺点主要有两个。第一是时间复杂度偏高。虽然O(n log n)在实际中表现不差但如果面试官问你“能不能一次遍历解决”排序法就不够看了。第二是它会修改原数组。qsort是原地排序如果你后续还需要用原数组的原始顺序那就得先拷贝一份再排序白白增加内存开销。排序法还有一个隐藏的小问题它必须保证数组中的元素互不相同的计数方式正确。比如[2, 2, 3, 1]排序后是[1, 2, 2, 3]从后往前扫先遇到 3计数 1再遇到 2计数 2再往前遇到 2和后面的 2 相同忽略再遇到 1计数 3返回 1。这个过程看上去没问题但你得在脑中多走几遍尤其是有连续相同元素的时候很容易数错。所以我会把排序法作为“验证答案”的方案而不是最终追求性能时的首选。下面来聊真正优雅的一次遍历方案。3. 解法二一次遍历维护前三大值优雅且省时3.1 核心思想三个格子滚动更新一次遍历法的思路说穿了就是维护三个变量第一大first、第二大second、第三大third。每读到一个数字就尝试把它放进这三个格子里同时保持它们从大到小排列。如果当前数字比first大那原来的first变成second原来的second变成third新的数字变成first。如果当前数字比first小但比second大那原来的second变成third新数字变成second。如果只比third大那直接更新third。这个过程很像排队。三个人按身高从高到低站好新来一个人如果最高就站最前面后面两个人依次往后挪如果身高介于中间就插到中间最后那个人出队如果只比最矮的高就把最矮的换掉。这种滚动更新的方式可以把时间复杂度降到O(n)只需要遍历一遍数组不需要额外排序也不需要额外内存。对于“找第 K 大”这类问题当 K 很小时这种多变量滚动维护的方案比堆排序更直观也更容易写对。3.2 哨兵值的正确选择这是大部分人的翻车点很多同学写这道题三个变量一开始都会初始化成INT_MIN然后遍历数组去更新。遇到测试用例[1, INT_MIN, 2]程序就傻眼了数组里第三个最大的数是INT_MIN但你初始哨兵值也是INT_MIN那怎么判断到底有没有找到第三大呢如果题目说“不存在第三大时返回最大值”可你又判断成了存在结果就会把INT_MIN当成第三大返回实际应该返回 2。解决这个问题有两种思路。第一种把哨兵值设成比任何可能的int都小的数比如long long类型的LLONG_MIN。因为题目给的是int数组元素转换成long long之后最小也只能是-2147483648而LLONG_MIN大概是-9223372036854775808两者之间隔了十万八千里永远碰不上。这样就可以放心用third LLONG_MIN来判断“是不是还没有第三大值”。第二种思路用额外的标志位记录“是否已经找到过真实的第三大”。这种方法不依赖特殊数值逻辑上也更安全但代码会多几行。在实际工程里我更喜欢哨兵值配合long long的写法因为它简洁而且只要选对类型就不会踩坑。这里顺便说一句为什么不用全局变量或者静态变量来做这件事。因为这道题要求函数可重入、可多次调用全局变量会保留上一次调用的状态导致结果错乱。老老实实把first、second、third定义成局部变量才是最稳的做法。3.3 完整代码示例与运行验证#include stdio.h #include limits.h int thirdMax(int *nums, int numsSize) { long long first LLONG_MIN; long long second LLONG_MIN; long long third LLONG_MIN; for (int i 0; i numsSize; i) { long long cur nums[i]; if (cur first || cur second || cur third) { continue; } if (cur first) { third second; second first; first cur; } else if (cur second) { third second; second cur; } else if (cur third) { third cur; } } if (third LLONG_MIN) { return (int)first; } return (int)third; }注意看第 8 行到第 10 行这是去重逻辑。如果当前cur已经等于三个变量中的任何一个说明这个值已经出现过直接跳过。这样[1, 2, 2, 3]这种用例才能正确处理第一个 2 会把second更新成 2第二个 2 因为已经记录过直接跳过不会干扰third的统计。更新顺序也不能乱。一定是third second; second first; first cur;先把旧数据往后挪再填新值。如果写成first cur; second first;那second拿到的就是新值而不是旧first整个队列就乱套了。我在本地跑过几组典型的测试数据结果如下int main(void) { int a[] {3, 2, 1}; int b[] {1, 2}; int c[] {1, 2, 2, 3}; int d[] {2, 2, 3, 1}; int e[] {1, 1, 1}; int f[] {1, INT_MIN, 2}; printf(%d\n, thirdMax(a, 3)); // 1 printf(%d\n, thirdMax(b, 2)); // 2 printf(%d\n, thirdMax(c, 4)); // 1 printf(%d\n, thirdMax(d, 4)); // 1 printf(%d\n, thirdMax(e, 3)); // 1 printf(%d\n, thirdMax(f, 3)); // -2147483648 return 0; }正好覆盖了正常情况、不足三个值、重复值、全相同值、包含INT_MIN等多种场景实测全部符合预期。4. 边界情况与测试用例把代码打服帖4.1 测试用例清单做算法题尤其是这种看起来平平无奇的题测试用例的覆盖度直接决定最终是否能通过。我整理了一个自测清单每次提交前都会在本地过一遍。输入数组期望输出验证点[3, 2, 1]1基础正常情况[1, 2]2不足三个不同值返回最大值[1, 2, 2, 3]1重复值不能重复计数[2, 2, 3, 1]1去重后第三大是 1[5, 5, 5]5全相同返回最大[1, INT_MIN, 2]INT_MIN数组本身包含 INT_MIN[1, 1, INT_MIN]1去重后不足三个返回最大 1[1, 2, 3, 4, 5]3普通多元素数组[-1, -2, -3]-3全负数负数也能排序和比较这个表里的用例尤其是第 6 行和第 7 行是我踩过坑之后才加进去的。很多人写排序法时不会出错但写一次遍历法时如果用INT_MIN当哨兵第 6 行必挂。4.2 逐条走查结果我自己逐条走查过一遍。先说排序法。对于[1, 2, 2, 3]排序后是[1, 2, 2, 3]从后往前遇到 3计数 1遇到 2计数 2再遇到 2和后面的 2 相等跳过遇到 1计数 3返回 1。正确。对于[5, 5, 5]排序后还是[5, 5, 5]从后往前第一个 5计数 1第二个 5相等跳过第三个 5相等跳过。循环结束计数仍然是 1返回最大值 5。正确。对于[1, INT_MIN, 2]排序后是[INT_MIN, 1, 2]从后往前2计数 11计数 2INT_MIN计数 3返回 INT_MIN。正确因为排序法根本不需要哨兵。一次遍历法则需要重点看第 6 行。[1, INT_MIN, 2]的处理过程是初始firstsecondthirdLLONG_MIN。读入 1大于 first于是thirdLLONG_MINsecondLLONG_MINfirst1。读入 INT_MIN转成 long long它不等于 first、second、third因为 LLONG_MIN 不等于 -2147483648也不大于任何变量所以三个值不变。读入 2大于 first于是thirdLLONG_MINsecond1first2。遍历结束thirdLLONG_MIN说明没有第三大值返回(int)first即 2。等等这里是不是有问题[1, INT_MIN, 2]去重后三个不同值是 2、1、INT_MIN第三大应该是 INT_MIN而不是 2。我前面写的期望结果是不是错了让我重新理一下这个用例。[1, INT_MIN, 2]元素有 1、-2147483648、2一共三个不同的值。从大到小排序2 最大1 第二大-2147483648 第三大。所以第三大确实是INT_MIN也就是 -2147483648。我的 main 函数里注释写的是// -2147483648是对的。但在刚才的走查里我推演到“读入 INT_MIN它不大于任何变量所以三个值不变”然后读入 2把 first 更新为 2second 更新为 1third 还是 LLONG_MIN。这就有问题了遍历结束后 third 是 LLONG_MIN程序会认为“没有第三大”返回 first2。但正确答案应该是 -2147483648。问题出在哪出在我推演时的数据顺序。遍历顺序是数组的原始顺序[1, INT_MIN, 2]。读入 1 时first1。读入 INT_MIN 时INT_MIN 不大于 first、second、third 中的任何一个所以不会更新。但事实上INT_MIN 应该是当前的第三大只是它并没有大于任何一个变量因为此时 second 和 third 都还是 LLONG_MIN比 INT_MIN 小。按我写的更新逻辑只有当 cur 大于 second 或者大于 third 时才会更新但 INT_MIN 小于 secondLLONG_MIN吗不对INT_MIN 是 -2147483648LLONG_MIN 是 -9223372036854775808INT_MIN 大于 LLONG_MIN。所以cur second是成立的LLONG_MIN 作为 second 的初始值此时 INT_MIN 确实大于它。按照代码逻辑应该进入else if (cur second)分支把thirdsecond也就是 LLONG_MINsecondcur也就是 INT_MIN。然后读入 22 大于 first1于是thirdsecondINT_MINsecondfirst1first2。遍历结束thirdINT_MIN 不等于 LLONG_MIN返回 INT_MIN。这样结果就对了。我刚才推演的时候漏掉了“INT_MIN 大于 LLONG_MIN”这个关键点所以以为它不会被更新。其实它会被更新成 second。这说明哨兵值用 LLONG_MIN 之后即使数组里包含 INT_MIN也不会出现误判因为 INT_MIN 会先被当作第二大的临时值记录进去后续再被更合适的值替换。这个例子的推演过程让我意识到写代码时不能凭感觉必须把每个比较都落到具体数值上尤其是涉及极端值的时候。4.3 两种方案的复杂度对比方案时间复杂度空间复杂度是否修改原数组代码量排序后去重O(n log n)O(1)或按 qsort 实现计 O(log n) 栈空间是较少一次遍历维护三值O(n)O(1)否适中一次遍历方案在时间上明显占优而且不改变原始数组这在某些场景下是硬性需求。排序方案胜在直观适合用来快速验证题意。如果你是在笔试环境里碰到这题我建议直接写一次遍历代码量不大又能体现你对边界条件的把控。5. 常见问题与调试心得5.1 问题速查表结合我带新人和自己刷题的经历这里整理一份高频问题速查表基本覆盖了这道题 90% 的报错场景。现象问题原因解决方案提交后结果偏大或随机比较函数中直接return x - y遇到INT_MAX和INT_MIN溢出改用(x y) - (x y)[1, 2, 2, 3]返回 2没有去重直接取倒数第三个位置遍历时只对与前一个不同的元素计数数组长度小于 3 时越界直接访问nums[numsSize-3]倒序计数不足三个返回最大值包含INT_MIN的用例出错用INT_MIN做哨兵值真假混淆改用long long和LLONG_MIN全相同数组返回不对去重计数逻辑写错跟踪distinctCount的变化过程一次遍历结果顺序颠倒更新first的顺序写反先thirdsecond; secondfirst; firstcur;5.2 几点排查经验第一如果你用 VS Code 或者其他编辑器调试遇到返回值不对不要急着加打印先在纸上模拟一遍三变量更新过程。这道题的逻辑链并不长手动走查三四个用例基本就能定位问题。我在给初学者讲的时候经常说一句话指针和数组的问题靠调试器这类“状态更新”的问题靠手写推演反而更快。第二注意函数签名中numsSize的类型。如果题目给的是int numsSize那在for循环里int i numsSize - 2没有问题。但如果你习惯写成size_t i就要小心numsSize - 2在无符号整数下变成很大的数导致循环直接越界。这是一个很隐蔽的坑不少人在数组长度小于 2 时翻车根因就在这里。第三提交前把测试用例清单跑一遍而不是只跑题目自带的示例。我在 4.1 节列出的那几张用例表就是我从错误提交记录里总结出来的。尤其是“包含INT_MIN”和“去重后不足三个不同值”这两类最容易被忽略也最影响结果。第四代码风格。三个变量的命名建议直接用first、second、third而不是a、b、c。命名越清晰你写更新逻辑的时候越不容易错。别小看这一点我在实际带项目时发现很多 bug 就是因为变量名太抽象导致思维混乱。最后分享一个我个人一直保留的习惯不管题目多简单提交前我都会用边界用例在脑内过一遍至少包括空数组如果不允许、单元素数组、全部相同、包含INT_MIN或INT_MAX的数组。这种习惯看着笨但真能帮你省下好几次因为边界条件被判错的返工时间。做这道“第三大的数”最大的收获不是会写排序和遍历而是明白了一个道理大多数 bug 不是出在主干逻辑上而是出在大家对“边界”这两个字的理解深浅不一样。把边界想清楚代码自然就稳了。