江川个人博客FIELD NOTES / 个人知识库

Article / 文章

LeetCode 第414题：第三大的数

给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数。

📖 文章摘要

本文详细解析LeetCode第414题“第三大的数”，这是一道考察数组处理和条件判断的题目。文章提供了多种解法，包含C#、Python、C++三种语言实现，配有详细的分析和性能对比。适合初学者和面试准备者。

核心知识点： 数组处理、排序、集合操作
难度等级： 简单
推荐人群： 编程初学者、面试准备者

题目描述

给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数。

示例

示例 1：

输入：[3, 2, 1]
输出：1
解释：第三大的数是 1 。

示例 2：

输入：[1, 2]
输出：2
解释：第三大的数不存在, 所以返回最大的数 2 。

示例 3：

输入：[2, 2, 3, 1]
输出：1
解释：注意，要求返回第三大的数，是指在所有不同数字中排第三大的数。
此例中存在两个值为 2 的数，它们都排第二。在所有不同数字中排第三大的数为 1 。

提示

  • 1 <= nums.length <= 10⁴
  • -2³¹ <= nums[i] <= 2³¹ - 1

进阶：你能设计一个时间复杂度 O(n) 的解决方案吗？

解题思路

方法一：排序去重法

最直观的解法，先去重排序，然后返回对应位置的数字。

关键点：

  1. 使用集合去重
  2. 排序后判断长度
  3. 返回正确的数字

具体步骤：

  1. 将数组转换为集合去重
  2. 对集合进行降序排序
  3. 判断集合长度是否大于等于3
  4. 返回第三大的数或最大的数

方法二：维护三个最大值

使用三个变量维护当前的三个最大值，只需要一次遍历。

关键点：

  1. 使用long类型避免整数边界问题
  2. 正确处理重复数字
  3. 维护三个变量的大小关系

图解思路

算法步骤分析表

步骤 操作 状态 说明
初始状态 - first=second=third=MIN 初始化三个变量
遍历数组 更新最大值 first=3,second=MIN 找到第一大的数
继续遍历 更新次大值 first=3,second=2 找到第二大的数
完成遍历 更新第三大值 first=3,second=2,third=1 找到第三大的数

状态/情况分析表

情况 输入 输出 说明
正常情况 [3,2,1] 1 存在第三大的数
不足三个数 [1,2] 2 返回最大值
有重复数字 [2,2,3,1] 1 重复数字只算一次
特殊情况 [1,1,2] 2 不存在第三大的数

代码实现

C# 实现

public class Solution {
    public int ThirdMax(int[] nums) {
        long first = long.MinValue;
        long second = long.MinValue;
        long third = long.MinValue;
        
        foreach (int num in nums) {
            if (num > first) {
                third = second;
                second = first;
                first = num;
            } else if (num < first && num > second) {
                third = second;
                second = num;
            } else if (num < second && num > third) {
                third = num;
            }
        }
        
        return third == long.MinValue ? (int)first : (int)third;
    }
}

Python 实现

class Solution:
    def thirdMax(self, nums: List[int]) -> int:
        nums = sorted(set(nums), reverse=True)
        return nums[2] if len(nums) >= 3 else nums[0]

C++ 实现

class Solution {
public:
    int thirdMax(vector<int>& nums) {
        long first = LONG_MIN;
        long second = LONG_MIN;
        long third = LONG_MIN;
        
        for (int num : nums) {
            if (num > first) {
                third = second;
                second = first;
                first = num;
            } else if (num < first && num > second) {
                third = second;
                second = num;
            } else if (num < second && num > third) {
                third = num;
            }
        }
        
        return third == LONG_MIN ? first : third;
    }
};

执行结果

C# 实现

  • 执行用时：84 ms
  • 内存消耗：39.8 MB

Python 实现

  • 执行用时：36 ms
  • 内存消耗：15.7 MB

C++ 实现

  • 执行用时：4 ms
  • 内存消耗：9.1 MB

性能对比

语言 执行用时 内存消耗 特点
C++ 4 ms 9.1 MB 性能最优，内存占用适中
Python 36 ms 15.7 MB 代码最简洁，性能适中
C# 84 ms 39.8 MB 实现清晰，内存占用较大

代码亮点

  1. 🎯 使用long类型避免整数边界问题
  2. 💡 优化比较逻辑，减少不必要的比较
  3. 🔍 正确处理重复数字和边界情况
  4. 🎨 代码结构清晰，变量命名规范

常见错误分析

  1. 🚫 未考虑整数边界问题
  2. 🚫 错误处理重复数字
  3. 🚫 未正确判断第三大的数是否存在
  4. 🚫 排序方法未考虑去重

解法对比

解法 时间复杂度 空间复杂度 优点 缺点
排序去重法 O(nlogn) O(n) 代码简单 性能较差
维护三个最大值 O(n) O(1) 性能最优 实现复杂

相关题目

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第414题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

  • 👍 点个赞，让更多人看到这篇文章
  • 📁 收藏文章，方便后续查阅复习
  • 🔔 关注作者，获取更多高质量算法题解
  • 💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！