LeetCode 414 第三大的数：去重细节与三种解法剖析

今天聊一道非常适合拿来当每日一题的经典题LeetCode 414第三大的数。别看题目名字直白它其实在“第几大”这个主题里埋了不少细节尤其是题干里那个很容易被忽略的限定词“不同”。我最初做这题时第一版代码不到十行一提交却错了原因就是没把重复数字处理好。这篇笔记会完整拆解题目规则、三种解法的取舍、最优解的原理以及我实际写码时踩过的坑希望对正在刷题或者准备面试的你有点帮助。这道题基本上属于“会者不难难者忽略条件”的典型。它在面试中出现的频率不算低因为代码量小、边界情况多非常适合考察候选人读题是否仔细、对复杂度有没有概念、能不能把一个看似简单的问题讲完整。你一旦掌握这题再往“第K大”“数据流中的第K大”延伸会发现思路是贯通的。1. 题目本身不复杂但三个细节决定生死1.1 原题到底在问什么题目原文可以概括成一句话给定一个非空整数数组返回数组中第三大的不同数字如果第三个最大的不同数字不存在则返回数组中最大的数字。我当初读题时注意力全在“第三大”这三个字上忽略了“不同”。后来复盘才意识到这道题的正确性完全取决于你对三件事的理解是否到位。第一数组是非空的。这看起来像废话但它意味着你不需要额外写空数组的防御逻辑。不过数组长度可能是1也可能是2这两种情况都必须正确处理。第二“第三大”指的是第三大的不同值。也就是说重复出现的数字只能算一个候选值。比如数组span [1, 2, 2, 3]不同数字只有1、2、3三个第三大是1。如果你不管“不同”直接按大小取倒数第三个会得到2这就是错的。第三返回值是数值本身不是下标也不是出现次数。面试时有人会把这道题和“找第三个最大元素的下标”混淆问出来的时候就知道题没读明白。1.2 “不同”两个字为什么能改变结果为了把这一点讲透我们来看两组对比。第一组是span [1, 2, 2, 3]。如果完全忽略“不同”把数组排序得到[1, 2, 2, 3]倒数第三个元素是2。但是把重复值去掉之后不同数字只有3、2、1第三大的不同值是1。同一个数组两种理解结果差了整整一档。第二组是 LeetCode 官方示例里的span [2, 2, 3, 1]。忽略“不同”的排序法和正确解法不一样但答案稍微巧一点这里我不展开具体数值你只要记住不同数字是3、2、1第三大是1就够。真正有意思的是下面这种[1, 1, 2]如果无视“不同”排序后是[1, 1, 2]倒数第三个是1。但去掉重复值之后不同数字只有2、1两个数量不足三个所以按题目规则应该返回最大值2。也就是说“不同”这个词不仅影响“第三大是谁”还会影响“第三大到底存不存在”。这种要命的细节必须在一开始就咬住。1.3 返回值规则的另一种理解我习惯把这道题的规则翻译成一句白话把所有不同的数字从大到小排成一列如果这一列至少有三个就返回第三个如果不够三个就返回第一个。更形式化一点设s是数组所有不同数字组成的集合。如果|s| 3答案就是把s按降序排列后的第三个数如果|s| 3答案就是max(s)。注意“不足三个就返回最大值”这一点很多人会理解成“返回第三大的不存在时按最大值兜底”这么说没错但实际代码里你要做的是判断第三大的位置有没有被填上而不是先排序再判断。这个区别在后面的三个变量解法里会体现得很明显。还有一个容易搞混的地方如果数组是[-1, -2, -3]第三大的不同值是-3不是-1。负数参与排序时很多人会被“最大值”“最小”绕晕实际上只要把所有数字按从大到小排位置关系完全一样。2. 三种解法从最笨到最优各自适合什么场景2.1 集合去重加排序五行的保守解法如果你只是想快速通过用例最直白的写法是这样def thirdMax(nums): uniq sorted(set(nums)) if len(uniq) 3: return uniq[-1] return uniq[-3]set(nums)负责去重sorted得到升序列表。uniq[-1]是最大值uniq[-3]是第三大的不同值。如果去重后不足三个就返回最后一位。这段代码的正确性很容易验证代价是时间复杂度O(n log n)空间复杂度O(n)。排序和集合都额外占内存对于这个题目来说属于“能过但不够漂亮”的方案。不过我不建议你直接跳过它。面试的时候这种解法有一个特殊作用它可以作为你思考路径的起点。你先说出“最朴素的做法是先去掉重复再排序取倒数第三个”然后分析它的复杂度再引出更优解法。这样面试官能看见你的思考过程而不是看到一个凭空冒出来的奇技淫巧。2.2 小顶堆加集合更接近“流式处理”的思路第二种解法是维护一个容量为 3 的小顶堆堆里始终保存当前已经遇到过的最大三个不同数字。小顶堆的堆顶是这三者中最小的一个也就是当前候选的第三大。每来一个数字x先看它是否已经出现过。如果出现过跳过如果没出现过就把它加入集合再根据堆的情况决定是否入堆import heapq def thirdMax(nums): heap [] seen set() for x in nums: if x in seen: continue seen.add(x) if len(heap) 3: heapq.heappush(heap, x) else: if x heap[0]: heapq.heapreplace(heap, x) if len(heap) 3: return max(heap) return heap[0]为什么x heap[0]才替换因为堆顶是当前三个最大候选里最小的那个也就是进入前三名的门槛。如果新数字连门槛都过不去它不可能排进前三如果它比门槛大那它就有资格顶掉门槛成为新的第三大。这里我用了一个seen集合来做重复判断。你可能会想既然堆里最多只有三个数字直接在堆里查重不就行了问题是堆不是按“是否包含某个值”设计的查重需要遍历整个堆虽然只有三个元素遍历起来不贵但逻辑上不够干净而且代码维护性差。用集合辅助查重虽然空间复杂度从O(1)变成了O(n)却换来了清晰的语义和扩展性。这个解法的时间复杂度是O(n log 3)因为堆大小固定可以近似看作O(n)。如果你把这个解法学会再去看“数据流中的第K大”这类题会觉得非常顺畅因为它们的骨架几乎一样只是堆的大小从 3 变成了k。2.3 三个变量单次扫描我最推荐的面试写法我认为这道题最优、也最符合面试直觉的写法是只用三个变量做一次扫描。思路是维护三个变量分别表示当前已经看到的数字里第一大、第二大、第三大的不同值是几。数组里每个元素进来都按照大小关系去尝试插入这三个变量组成的有序序列如果它跟已有变量相等就直接跳过因为重复值不会改变任何排名。def thirdMax(nums): first second third None for x in nums: if x first or x second or x third: continue if first is None or x first: first, second, third x, first, second elif second is None or x second: second, third x, second elif third is None or x third: third x return first if third is None else third这段代码看起来短但里面有几个关键点为什么用None而不是一个很大的负数为什么if x first or x second or x third要放在最前面为什么赋值顺序是first, second, third x, first, second这些问题我放到第 4 节专门讲这里先记住结论。复杂度上它是O(n)时间、O(1)空间没有任何额外数据结构。对于“第三大”这种固定规模问题这就是最优解也最能体现你对空间复杂度的控制能力。2.4 三种解法放在一起怎么选解法时间复杂度空间复杂度优点缺点集合去重加排序O(n log n)O(n)代码最少正确性一目了然大数组性能差面试不够亮眼小顶堆加集合O(n log 3)O(n)可以顺势扩展成第K大接近流式处理需要额外维护堆逻辑稍多三个变量单次扫描O(n)O(1)最优复杂度代码干净无额外结构哨兵值和变量更新顺序必须一次写对我自己做这道题时三种写法都验证过也都跑过完整测试。结论是如果是为了通过题目或者面试手写三个变量法综合性价比最高如果你想借这道题顺便复习“第K大”和“流式处理”那堆的解法更有价值。两者不冲突你可以都掌握。3. 三个变量法为什么是对的不变量与逐步推演3.1 不变量到底是什么很多人刷题只背代码不理解背后的不变量导致面试时稍微被追问两句就露馅。三个变量法的不变量是这样一句话每处理完数组里的前i个元素之后first、second、third分别等于前i个元素去重后的第一大、第二大、第三大如果某个排名暂时还不存在对应变量就是None。这个不变量在循环开始前是成立的因为一个元素都没处理时三个位置都没有候选。每次迭代结束时我要保证它依然成立。只要你能做到这一点扫描完整数组后三个变量自然就持有了全局答案。而这正好解释了为什么相等判断不能省。如果first、second、third已经各自维护着三个互不相同的值来一个和first相等的数它当然不会改变排名但如果少了这步判断它可能会被错误地插进second或third的位置把第二、第三名污染成和第一名相同的值不变量就被破坏了。3.2 三种分支的情况我们逐个看新元素x进入时会发生什么。第一种情况x比first大或者first还是None。这说明x是新的最大值。原来的first降为第二名原来的second降为第三名原来的third被挤出去。于是写first, second, third x, first, second这里有个细节等号右边的first、second是旧值。Python 会先把右边所有表达式求值再执行赋值所以不会出现“覆盖了旧值导致后面取不到”的问题。第二种情况x不大于first但比second大或者second还是None。这说明x应该排在第一名和当前第二名之间。原来的second降为第三名原来的third被挤掉second, third x, second第三种情况x只比third大或者third还是None。说明它只能排在第三名third x因为三个分支是互斥的而且每次更新后都保持了“从大到小、互不相同、前三个候选”这三个性质所以循环结束后答案就是first或third。为了直观一点你可以拿[5, 1, 4, 3]自己在纸上走一遍。前两个元素让first5, second1第三个元素4插在中间让second4, third1第四个元素3只比third大所以最终third3。不同数字降序是5、4、3第三大确实是3。3.3 为什么三个变量就够不需要第四个这是面试官最喜欢追问的问题。答案是题目最终只要第三大的值这个值只依赖前三大的三个不同数字。任何排在第四名及更后面的数字都不会影响前三名的组成。你可以反过来想如果维护四个变量会不会改变答案不会。第四个位置唯一可能被用到的情况是第三名被挤出后新的第三名需要某个值填充但新第三名要么来自原来的第二名要么来自新来的元素压根不需要旧第四名。所以三个变量就是刚好够用的状态这也是O(1)空间的底气来源。如果题目改成“返回第四大的不同数字”那就要再多维护一个变量或者干脆改用大小为 4 的堆。规律是要找第k大就需要维护前k大。固定k时用变量不固定时用堆。4. 写代码时最容易掉进去的坑以及我怎么避开的4.1 哨兵值为什么我不用负无穷用 None网上很多版本的三个变量解法会用float(-inf)作为初始值然后循环结束后检查third是否还是负无穷来判断第三大是否存在# 这种写法有隐患 def thirdMax(nums): first second third float(-inf) for x in nums: if x first: first, second, third x, first, second elif x second: second, third x, second elif x third: third x return first if third float(-inf) else third这段代码跑 LeetCode 原题大概率能过因为测试数据是整数数组不会出现负无穷。但它把“第三大不存在”和“第三大恰好等于一个特定值”这两种情况混在一起了。假设某个业务系统允许输入float(-inf)那当数组是[1, 2, float(-inf)]时正确答案应该返回float(-inf)但上面的代码会以为第三大不存在错误地返回1。我更推荐用None表示“还没填上”因为None不会和任何整数相等判断逻辑从“值比较”变成了“状态判断”语义更清晰。4.2 重复判断必须放在最前面重复判断不是为了优化速度而是为了维持变量之间的互异性。来看一个反例。数组[3, 3, 2, 1]正确答案是多少不同数字是3、2、1第三大是1。如果没有最前面的continue去重代码会怎么执行第一个3让first3第二个3进来时因为x first不成立而second is None成立它会被塞进second于是first3, second3。接着2填进third最后返回2。这就是错误答案。真正正确的结果应该是1因为第二个3是重复值它不应该占据第二名的位置。所以if x first or x second or x third: continue不是可选优化是必要逻辑。4.3 变量更新顺序写反是高频错误如果不用 Python 的元组赋值很容易写错成# 错误示例 first x second first third second第一次更新没问题但第二次更新时second拿到的已经是新的first而不是旧的first。这样会导致两个变量存同一个值整个算法就废了。正确的等价写法是先用临时变量保存旧值old_first, old_second first, second first x second old_first third old_second这种写法更直白适合不习惯元组赋值的人。其实很多看起来“巧妙”的代码本质上就是做了这么一件事先取旧值再按优先级往下移动。想清楚这一点你怎么写都不会错。5. 从“第三大”到“第K大”以及流式场景的延伸5.1 改成第K大之后的写法三个变量法只适用于k3。如果题目改成“返回第k大的不同数字”最佳方案是堆。因为k可能是任意值你不可能写几百个变量。import heapq def kth_largest_distinct(nums, k): heap [] seen set() for x in nums: if x in seen: continue seen.add(x) if len(heap) k: heapq.heappush(heap, x) else: if x heap[0]: heapq.heapreplace(heap, x) if len(heap) k: return max(heap) return heap[0]这个版本时间复杂度O(n log k)空间复杂度O(n)。当k很小且固定时三个变量法更高效当k动态变化或者输入是流式数据时堆的写法更通用。5.2 堆顶为什么是“门槛”而不是“答案”使用小顶堆找第k大有一个非常容易混淆的点堆顶到底是答案还是门槛答案是两者可以是同一件事。在维护过程中堆顶是当前k个最大候选里的最小值也就是进入前k名的门槛。新元素只有超过门槛才能进来替换掉门槛然后产生新的门槛。等到所有数据处理完这个门槛同时也就是第k大的答案。有人会问为什么不用大根堆因为大根堆的堆顶是当前集合里的最大值你拿到最大值却不知道第k名是谁也不知道该踢掉谁。只有小根堆能把“最小的阈值”暴露在堆顶让你在常数时间内完成淘汰决策。这是 top-k 问题的一个核心考察点。5.3 真实场景和内存权衡这种维护 top-k 的思路在很多真实系统里都有影子排行榜、热门关键词、游戏里的全局分数榜、日志系统里的 TOP 错误数。它们共同的特点是不能反复排序数据源源不断进来而且内存有限。解法基本就是“固定大小的堆 辅助去重结构”。但在真实系统里去重结构如果无限增长内存也会爆掉。常见的妥协方案包括只在一个时间窗口内去重窗口过期就清空seen或者允许少量近似误差不严格去重改用布隆过滤器。面试时能讲到这一层分数通常不会低。5.4 面试中怎么把这道题讲清楚我建议按这个顺序回答先复述题目并确认“不同”“不存在时返回最大值”这两个关键词接着给出最朴素的排序方案分析O(n log n)然后引出三个变量法说明用三个变量维护去重后的前三名分析O(n)时间和O(1)空间最后关于下界多说一句因为每个数字都可能影响前三名的结果所以至少需要扫描一遍数组O(n)已经是下界。这套话术很顺而且每句话都有信息量面试官很难挑出毛病。6. 杰瑞的每日一题为什么这题值得刷进收藏夹最后落到我的每日一题经验上。这道题我刷题时遇到过也在模拟面试中给别人讲过每次都能发现新的表达盲区。它的价值不在于让你背会一个答案而在于训练三件事。第一读题要抓限定词。“不同”两个字决定了去重逻辑“不足三个返回最大值”决定了兜底逻辑。你可以在写代码前先大声把题意复述一遍复述不顺说明还没读懂。第二写算法要讲复杂度。排序法和三个变量法的时间复杂度差了一个数量级在面试环境里这个差别就是你跟其他候选人的距离。能说出“为什么 O(n) 是这个问题的下界”比单纯写出正确答案更能体现水平。第三边界用例要主动构造。我整理了一份我实际用来测试这道题的用例表你可以直接拿去跑输入数组预期输出测试意图[3, 2, 1]1基础正例[1, 2]2不同数字不足三个[2, 2, 3, 1]1存在重复值[1, 1, 2]2重复导致第三大不存在[1, 2, 3, 4]2正常四个不同值[-1, -2, -3]-3全是负数[5, 5, 5]5全部相同每次我写完这种“看起来很简单”的题都会顺手把“三数之和”或“数据流中的第K大”再翻出来做一遍。因为它们的底层思维是相通的要么维护固定数量的状态要么维护一个固定大小的堆。把这三个题放在一起类比你对整个 top-k 主题的记忆会牢固得多。最后再分享一个小习惯我会把每天的题解笔记分成“读题关键点”“解法演进”“避坑记录”三块。看起来费时间但半年以后再回看这些笔记你会发现自己对算法题的理解早就不是当初那个只会排序取倒数第三的家伙了。