C语言数组第三大数求解：去重与边界条件全解析

这两天有个正在准备复试的朋友给我发来一道题，题目非常简单，就一句话——“给定一个非空数组，返回数组中第三大的数。如果不存在，则返回数组中最大的数。”他说自己用排序写完之后，总觉得哪里不对劲，但又说不出哪里不对。我一看就明白了，这道题表面上是个入门题，实际上埋了至少三个雷：一个是“第三大”指不包含重复元素的第三大，一个是数组元素可能是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也被更新成3，third被更新成原先的1，最终结果变成1。看起来好像没错，但如果你换一组数据[3, 3, 2]，没有这行时，第一个3填进first，第二个3会走else if (nums[i] > second)分支（因为第二个3等于first但大于second），把third更新成原来的second（LLONG_MIN），second更新成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 = -2147483648，b = 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 边界用例如表

写代码时，比“实现功能”更值钱的是“定义测试用例”。这道题的边界条件集中在重复元素、空值和极小值上。我整理了一组测试，直接贴代码里当自测用例：

其中第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_MIN，second = first = INT_MIN，first = 1。
• 遍历到2，进入nums[i] > first分支，third = second = INT_MIN，second = first = 1，first = 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文件里，用-std=c11 -Wall -Werror编译。-Wall会把可疑的写法都警告出来，-Werror把警告当错误处理，这能逼着你写出更干净的代码。C语言的很多问题不到编译警告那个级别根本发现不了，开满警告选项是一个性价比极高的好习惯。