这两天有个正在准备复试的朋友给我发来一道题题目非常简单就一句话——“给定一个非空数组返回数组中第三大的数。如果不存在则返回数组中最大的数。”他说自己用排序写完之后总觉得哪里不对劲但又说不出哪里不对。我一看就明白了这道题表面上是个入门题实际上埋了至少三个雷一个是“第三大”指不包含重复元素的第三大一个是数组元素可能是INT_MIN本身还有一个是遍历顺序对结果的影响。这篇文章我就用C语言把这道题从头到尾拆一遍讲清楚为什么排序不是最优解以及不排序时怎么用三个变量把前三大稳稳地维护住。先说清楚解题之前必须搞清楚的事情第三大的数到底按什么规则来算。力扣和不少笔试平台给的题目有明确的“去重”要求也就是说第三大的数是数组中不同的三个数里第三大的那个。举个例子[1, 2, 2, 3]去重之后是[1, 2, 3]第三大就是1但如果你不去重直接排序那么第三大的位置上是2这就错了。很多人在这一步栽跟头不是因为不会写代码是因为压根没意识到“第三大”有歧义。还有一句“如果不存在则返回最大的数”这句话也很容易理解偏不是指数组长度小于3才不存在而是指去重之后不足三个数就算不存在。比如[1, 1, 2]去重后只有1和2两个数此时按要求应该返回最大的数2而不是某个不存在的“第三大”。1. “第三大”到底在问什么先搞清楚题目里的三个隐藏陷阱1.1 陷阱一第三大不等于排序后倒数第三个数这是整个题目最核心的认知偏差。大多数人拿到题目后第一反应是先排序然后从尾部开始数第三个不就完了吗用快速排序或者C标准库里的qsort十行代码搞定。如果你不追求效率、也不在乎重复元素这确实能过。但题目如果明确写了“第三大的数”而没说“排序后从后往前数第三个”那你就要小心了。我们需要讨论一个非常具体的语义第三大的“大”怎么定义。在数学上“第一大”就是最大值“第二大”就是在去掉最大值之后剩下的最大值“第三大”就是再去掉前两大之后剩下的最大值。注意这个“去掉”指的是把数值相同的所有元素一起去掉。所以[3, 2, 1]的第三大是1[3, 3, 2, 2, 1, 1]的第三大还是1因为相同数值只算一个。两个3只算一个“3”两个2只算一个“2”两个1只算一个“1”一共才三个不同的值第三大就是1。这一点如果不先达成共识后面写的代码一定是错的。我见过很多人用排序法做完之后发现[1, 2, 2, 3]测试不通过然后一脸困惑。根因就是排序处理的是“位置”而题目要的是“去重后的值”。1.2 陷阱二不存在第三大时返回的是最大值题目里这句话容易被当成废话但它实际上是整个题目最容易遗漏的边界条件。什么情况下不存在第三大不是长度不够而是去重之后不足三个数。也就是说数组可能是很长的[5, 5, 5, 5, 5]但去重只剩一个5此时没有第三大返回最大值5。数组[2, 2, 1]去重后只有2和1也没有第三大返回2。很多解法在实现时习惯把三个变量初始化为INT_MIN然后遍历数组维护前三大。如果数组长度大于等于3且元素互不相同这没问题但如果数组里恰好有一个INT_MIN本身的元素你的“第三大”就和“初始值”混淆了就会返回一个错误答案。这一点我会在第三节详细展开这里先记住结论任何用特殊值充当“无穷小”或“空位”的初始化方案都必须额外加标志位来区分“还没赋值”和“真的是这个值”。1.3 陷阱三维护前三大时更新顺序不能乱如果你决定不排序、用一遍遍历来维护三个变量那可不可能边比较边更新可能但顺序写反就废了。比如你先更新了最大值再用更新后的最大值去比第二大的数那么第二大的数永远是旧最大值逻辑直接崩溃。所以必须倒着更新先判断是否大于第三大再判断是否大于第二大最后判断是否大于第一大。顺序错一步整个维护过程就失效。这个道理放在实际生活中很容易理解你有一个排行榜来了一个新成绩要插入前三名你得先把第三名挤掉再把第二名变成第三名、第一名变成第二名最后把新成绩放在第一名。如果你先把第一名挤掉那原本的第二名就找不到了。更新前三大变量和更新排行榜是一个逻辑。2. 不排序的解法三个变量如何稳稳维护前三大2.1 为什么排序不是首选再往前一步我们先明确一下排序方案的代价。用C标准库的qsort排序时间复杂度是O(n log n)空间复杂度取决于实现通常是O(n)或O(log n)。如果数组长度是10^5排序完全没问题如果是10^7排序就已经很吃力了。而这道题只要求第三大你完全可以只遍历一遍用O(n)时间、O(1)空间解决。从算法设计的角度来说这才是有区分度的解法。笔试和面试里出题人更想看到的是你有没有“维护前K个极值不需要排序”的意识。当然我也不是完全否定排序法。如果题目明确允许排序或者输入规模极小排序法确实更简单、更不容易写错。但在生产级的代码里没人会为了拿第三大的数去把整个数组排序这个习惯很不好。能用一遍遍历解决的事就不要把数据全部重新排列一遍。2.2 三个变量 倒序更新的核心代码我们直接上代码。为了把“去重”这个逻辑融入其中比较大小的时候要带上等号等于当前值的情况直接跳过不去更新任何变量。具体写法如下#include stdio.h #include limits.h int thirdMax(int* nums, int numsSize) { // 用 long long 而不是 int是为了避免和元素真实出现的 // INT_MIN/LLONG_MIN 混淆long long 足够表示所有 int 值。 long long first LLONG_MIN; long long second LLONG_MIN; long long third LLONG_MIN; for (int i 0; i numsSize; i) { // 重复元素直接跳过保证“去重”语义 if (nums[i] first || nums[i] second || nums[i] third) { continue; } if (nums[i] first) { third second; second first; first nums[i]; } else if (nums[i] second) { third second; second nums[i]; } else if (nums[i] third) { third nums[i]; } } // 如果第三大从未被更新过说明去重后不足三个数返回最大值 if (third LLONG_MIN) { return (int)first; } return (int)third; }你可能注意到这里有个关键设计我声明成了long long而不是int初始值用LLONG_MIN而不是INT_MIN。这和我前面埋的陷阱二直接相关如果数组里有一个元素恰好是INT_MIN并且它真的是第三大的数那它和初始化的“空值”INT_MIN会撞车你根本分不清这个third是被更新过的INT_MIN还是从未更新的INT_MIN。而long long的范围比int大得多任何一个int值都不可能等于LLONG_MIN所以LLONG_MIN永远只表示“空位”。这在C语言里是一个非常常见的技巧把哨兵值选在目标类型范围之外避免和目标类型的真实值混淆。2.3 为什么不会出现 first 和 second 相同的情况刚才的代码里有一句if (nums[i] first || nums[i] second || nums[i] third) continue;这行非常关键。假设没有这行当数组是[3, 1, 2, 3]时遍历到末尾那个3它大于second但等于first代码会错误地把它当成“新的第二大”来更新导致second也被更新成3third被更新成原先的1最终结果变成1。看起来好像没错但如果你换一组数据[3, 3, 2]没有这行时第一个3填进first第二个3会走else if (nums[i] second)分支因为第二个3等于first但大于second把third更新成原来的secondLLONG_MINsecond更新成3最后third是LLONG_MIN你判断“不存在第三大”之后返回最大值3这道题好像也能碰巧过。但如果数组是[3, 1, 3, 2]没有去重判断时第二个3会把third更新成1原来的second之后遍历到2时会更新成2最后返回2看起来又没错。我举这些例子的意思是如果不去重很多测试用例可能碰巧对也可能错完全取决于元素出现的顺序。这种“时对时错”要比“一直错”更可怕因为你会误以为自己的逻辑没问题。所以把去重判断写进循环体不是可选项是必须项。你只在最终判断前做一次去重是不够的因为三个变量在更新过程中会被反复覆盖必须在一开始就把相等的值过滤掉才能保证前三个变量始终是“三个不同值”的前三大。3. 排序方案的思路与局限能跑通但别用在大数据上3.1 升序排序后从尾向前找“第三不同值”如果你确实想用排序方案怎么把去重逻辑做对这里我给出一个标准的C语言实现它很好的示范了“先排序再去重取数”的思路。#include stdio.h #include stdlib.h int cmp(const void* a, const void* b) { // 升序排序 return (*(int*)a - *(int*)b); } int thirdMaxSort(int* nums, int numsSize) { qsort(nums, numsSize, sizeof(int), cmp); // 从尾部向前找不同的数 int distinctCount 1; for (int i numsSize - 1; i 0; i--) { if (nums[i] ! nums[i - 1]) { distinctCount; if (distinctCount 3) { return nums[i - 1]; } } } // 不足三个不同值返回最大值 return nums[numsSize - 1]; }这段代码的思路是升序排完后数组末尾是最大值。从末尾开始向左移动只要发现相邻元素值不同就说明遇到一个“新的更小”的值。数到第三个不同的值时那个位置就是第三大的数。如果从头走到尾都没数够三个不同值就返回末尾最大值。这个方案的时间复杂度是O(n log n)空间复杂度是O(1)不考虑qsort递归栈开销时。它的优点是逻辑直观、不容易犯“变量初始化”的错缺点也很明显它在处理海量数据时很浪费而且如果你要在一个嵌入式环境里用C语言处理一个超大数组比如单片机采样数据qsort的递归栈和排序开销都是你不想承担的。3.2 排序法里最容易被忽略的问题cmp比较函数的整形溢出上面cmp函数里有一行return (*(int*)a - *(int*)b);这在绝大多数情况下没问题。但这其实是一个经典的C语言陷阱当两个int相减的结果超出int范围时会发生有符号整数溢出其行为是未定义的。比如a -2147483648b 2147483647相减结果是-4294967295远超出int能表示的范围此时一切皆有可能。虽然qsort的cmp返回值的绝对值大小无关紧要只要是负的、0、正的就行但溢出可能让符号改变从而破坏排序正确性。安全的写法是这样的int cmp(const void* a, const void* b) { int x *(const int*)a; int y *(const int*)b; if (x y) return -1; if (x y) return 1; return 0; }或者用long long做差再夹逼。这在刷题时不一定暴露但在企业级代码里数据范围和输入规模一上来这种隐藏bug会极其恶心。所以我在给朋友讲这道题时特意把这个坑翻出来因为C语言里“排序比较器”是最容易写出未定义行为的地方之一。3.3 排序方案在哪些场景下才值得使用排序法并非一无是处。如果题目不是让你返回第三大的数而是让你返回第k大的数且k比较大比如第五大、第十大你再维护三个变量就不够用了这时候要么用堆要么排序后随机访问。面试题里有一类变体是“返回第k大的元素”那就需要用到快速选择算法或者大小为k的小顶堆。所以第三大的数本质上是一个“小规模的‘第k大’问题”因为k固定为3所以可以用常数个变量解决。如果你以后要写“第k大”再把堆或者快选拿出来用这个分级思维非常重要。4. 边界条件与测试用例设计用一组用例把所有Bug逼出来4.1 边界用例如表写代码时比“实现功能”更值钱的是“定义测试用例”。这道题的边界条件集中在重复元素、空值和极小值上。我整理了一组测试直接贴代码里当自测用例输入数组期望结果你的程序应该怎么走[3, 2, 1]1三个互不相同第三大是1[1, 2]2去重后不足3个返回最大[2, 2, 3, 1]1两个2只算一个去重后是3、2、1[1, 2, 2, 3]12重复第三大是1[1, 1, 2]2只有两个不同值返回最大2[3, 3, 3]3去重后只剩一个数返回3[-2147483648, 1, 2]-2147483648数组包含INT_MIN第三大是INT_MIN[2147483647, 2147483647, 2147483646]2147483646重复最大值不影响返回第二不同值其中第7组最重要。很多用int型变量初始化为INT_MIN的解法在这组用例上会直接返回1或2因为它们的third坚持认为INT_MIN是“还没赋值”。而如果你的初始值用long long的LLONG_MIN这组就能安全通过。4.2 调试一个真实翻车案例INT_MIN初始化导致结果的覆灭我让朋友把他最初的错误代码发给我他是这样写的int thirdMaxWrong(int* nums, int numsSize) { int first INT_MIN; int second INT_MIN; int third INT_MIN; for (int i 0; i numsSize; i) { if (nums[i] first) { third second; second first; first nums[i]; } else if (nums[i] second) { third second; second nums[i]; } else if (nums[i] third) { third nums[i]; } } if (third INT_MIN) { return first; } return third; }他在本地测试[-2147483648, 1, 2]时程序返回了1。为什么因为初始first second third INT_MIN。遍历到-2147483648它不大于first、不大于second、不大于third所以什么也没发生。严格说这一步没问题因为-2147483648还未被当作“新的”前三大但由于它等于初始哨兵算法无法把它记录下来。遍历到1进入nums[i] first分支third second INT_MINsecond first INT_MINfirst 1。遍历到2进入nums[i] first分支third second INT_MINsecond first 1first 2。最终third INT_MIN程序认为“不存在第三大”返回first 2。不只是返回错误甚至返回的2也不是“最大值所在位置应该返回-2147483648”的意义。这组用例直接就把错误方案打回原形。所以如果你的解法用INT_MIN作哨兵除非你给三个变量各加一个“是否已赋值”的布尔标志否则不可能正确区分“空位”和“真实存在的INT_MIN”。4.3 用标志位方案的备选写法如果你不想用long long换数据类型也可以给每个变量配一个布尔标志表示“这个位置是否有真实值”。具体写法是int thirdMaxWithFlag(int* nums, int numsSize) { int first, second, third; int hasFirst 0, hasSecond 0, hasThird 0; for (int i 0; i numsSize; i) { int val nums[i]; // 去重如果已经在前三位中出现过跳过 if ((hasFirst val first) || (hasSecond val second) || (hasThird val third)) { continue; } if (!hasFirst || val first) { third second; hasThird hasSecond; second first; hasSecond hasFirst; first val; hasFirst 1; } else if (!hasSecond || val second) { third second; hasThird hasSecond; second val; hasSecond 1; } else if (!hasThird || val third) { third val; hasThird 1; } } if (!hasThird) { return first; } return third; }这个方案不依赖任何类型范围可读性也不错。我在代码评审里见过不少类似的维护前K个元素的写法标志位法在语义上是最清晰的。但它的行数明显比long long哨兵版多需要在注释里多写几句否则维护者容易迷路。两个方案都可以我一般倾向long long哨兵版因为它代码短且C语言标准里long long最大范围完全盖过int。5. 从这道题延伸出的C语言功底考点与复盘5.1 基础语法之外题目在考什么第三大的数本身是一个算法题但它出现在C语言学习或笔试场景中时通常还想考察下面几件事是否清楚INT_MIN和LLONG_MIN这类极限值宏的定义与使用。是否了解有符号整数溢出的危险性。能否平衡“代码简洁”和“语义安全”。能否处理边界条件尤其是重复元素。是否具备“先设计测试用例再写代码”的习惯。我看到很多教程在讲这道题时只给一个排序或者一个三变量方案就结束了却不解释为什么不排序、为什么初始值不能用INT_MIN、为什么更新要从后往前。这些才是真正的经验积累也是笔试后和面试官聊起来最有价值的点。5.2 如果数据量极大三个变量还够用吗有一种变体是“从多路数据流中实时统计第三大的数”每来一个数字就调用一次更新接口这时候你维护三个变量依然是O(1)空间比维护一个有序数组更省。这是这道题在生产系统里的现实意义你不需要对所有历史数据做全量排序只需要维护几个极值就能回答很多统计问题。比如某个监控系统要追踪全网第三大的连接数、某个排行榜要维护前三名都可以用同样的套路。当然如果前K中K很大就要换成大小为K的小顶堆这个进阶方向你在理解了3个变量的维护逻辑后再去想会很自然。另外在嵌入式C语言开发场景里内存极其有限数组可能很大你不可能申请一个额外的拷贝来做排序。这时候三变量法几乎是唯一合理的选择。我实际做单片机上的滑动窗口数据处理时经常用类似思路维护窗口内最大、次大、第三大然后根据第三大的值决定是否触发某种限幅或报警策略。每次只有新数据进来就执行一次倒序更新开销极小实时性非常好。5.3 刷完这题之后你可以继续做哪些变体如果这道题你已经完全吃透了我建议你再刷几个相关变体它们本质上一脉相承数组中的第K个最大元素模板是快速选择或大小为K的小顶堆这题会让你理解为什么第K大不能靠固定几个变量硬算。找出数组中出现频率第三高的元素哈希表统计频率之后再维护前三大频率这需要结构体数组和排序或维护逻辑结合。数据流的中位数这是用两个堆最大堆最小堆维护动态中位数前K大/K小的进阶版本。合并K个有序链表/数组涉及到堆、多路归并和前面“实时统计极值”的思路其实相通。每做完一个变体都可以回来想一个问题如果第三大的数不让我排序也不让我用额外数组我能不能在O(log n)的更新代价内维护这就是工程优化的思路了。你先从这道题的O(1)空间三变量解法里体会到“数据压缩”的快乐再有兴趣去研究更复杂的堆结构会更顺。5.4 收尾复盘一个老生常谈却很实用的代码习惯最后说个题外话。我给朋友讲完这道题以后让他把测试用例也写到注释里。很多人刷题时只在本地跑一两次就提交一旦出问题又开始凭感觉改代码这是效率最低的调试方式。你应该把每个测试用例连同期望结果一起记录下来改完代码后全部重新跑一遍确保没有“按下葫芦浮起瓢”的情况。尤其是像[INT_MIN, 1, 2]这种用例很可能你修好一个地方又把另一个地方改坏了。测试用例是比代码更重要的资产这个习惯从刷题阶段就养成以后写工程代码会少无数个深夜。如果你现在用的是VS Code GCC的环境可以直接把上面thirdMax和main函数放在一个main.c文件里用-stdc11 -Wall -Werror编译。-Wall会把可疑的写法都警告出来-Werror把警告当错误处理这能逼着你写出更干净的代码。C语言的很多问题不到编译警告那个级别根本发现不了开满警告选项是一个性价比极高的好习惯。