英文原文
Given an integer array nums, return the third distinct maximum number in this array. If the third maximum does not exist, return the maximum number.
Example 1:
Input: nums = [3,2,1] Output: 1 Explanation: The first distinct maximum is 3. The second distinct maximum is 2. The third distinct maximum is 1.
Example 2:
Input: nums = [1,2] Output: 2 Explanation: The first distinct maximum is 2. The second distinct maximum is 1. The third distinct maximum does not exist, so the maximum (2) is returned instead.
Example 3:
Input: nums = [2,2,3,1] Output: 1 Explanation: The first distinct maximum is 3. The second distinct maximum is 2 (both 2's are counted together since they have the same value). The third distinct maximum is 1.
Constraints:
1 <= nums.length <= 104-231 <= nums[i] <= 231 - 1
Follow up: Can you find an
O(n) solution?中文题目
给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数。
示例 1：
输入：[3, 2, 1] 输出：1 解释：第三大的数是 1 。
示例 2：
输入：[1, 2] 输出：2 解释：第三大的数不存在, 所以返回最大的数 2 。
示例 3：
输入：[2, 2, 3, 1] 输出：1 解释：注意，要求返回第三大的数，是指在所有不同数字中排第三大的数。 此例中存在两个值为 2 的数，它们都排第二。在所有不同数字中排第三大的数为 1 。
提示：
1 <= nums.length <= 104-231 <= nums[i] <= 231 - 1
进阶：你能设计一个时间复杂度 O(n) 的解决方案吗？
通过代码
高赞题解
Set 去重 + 排序
题目要求返回含重复元素的数组 $nums$ 中的第三大数。
一个朴素的做法是，先使用 Set 对重复元素进行去重，然后对去重后的元素进行排序，并返回第三大的元素。
代码：
[]class Solution { public int thirdMax(int[] nums) { Set<Integer> set = new HashSet<>(); for (int x : nums) set.add(x); List<Integer> list = new ArrayList<>(set); Collections.sort(list); return list.size() < 3 ? list.get(list.size() - 1) : list.get(list.size() - 3); } }
- 时间复杂度：使用
Set去重的复杂度为 $O(n)$；排序复杂度为 $O(n\log{n})$。整体复杂度为 $O(n\log{n})$ - 空间复杂度：$O(n)$
有限变量 + 遍历
经典的找数组次大值的做法是使用两个变量 a 和 b 分别存储遍历过程中的最大值和次大值。
假设当前遍历到的元素为 $x$，当满足如下条件时，考虑更新 a 或者 b:
- 当 $x > a$ 时，说明最大值被更新，同时原来的最大值沦为次大值。即有 $b = a; a = x;$
- 在条件 $1$ 不满足，且有$x > b$ 时，此时可以根据是否有「严格次大值」的要求，而决定是否要增加 $x < a$ 的条件：
- 不要求为「严格次大值」：直接使用 $x$ 来更新
b，即有 $b = x$； - 当要求为「严格次大值」： 此时需要满足 $x < a$ 的条件，才能更新
b。
- 不要求为「严格次大值」：直接使用 $x$ 来更新
回到本题，同理我们可以使用 a、b 和 c 三个变量来代指「最大值」、「严格次大值」和「严格第三大值」。
从前往后遍历 $nums$，假设当前元素为 $x$，对是否更新三者进行分情况讨论（判断优先级从上往下）：
- $x > a$，说明最大值被更新，将原本的「最大值」和「次大值」往后顺延为「次大值」和「第三大值」，并用 $x$ 更新
a； - $x < a$ 且 $x > b$，说明次大值被更新，将原本的「次大值」往后顺延为「第三大值」，并用 $x$ 更新
b； - $x < b$ 且 $x > c$，说明第三大值被更新，使用 $x$ 更新
c。
起始时，我们希望使用一个足够小的数来初始化 a、b 和 c，但由于 $num[i]$ 的范围为 $[-2^{31}, 2^{31} - 1]$，因此需要使用 long 来进行代替。
返回时，通过判断第三大值是否为初始化时的负无穷，来得知是否存在第三大值。
代码：
[]class Solution { long INF = (long)-1e18; public int thirdMax(int[] nums) { long a = INF, b = INF, c = INF; for (int x : nums) { if (x > a) { c = b; b = a; a = x; } else if (x < a && x > b) { c = b; b = x; } else if (x < b && x > c) { c = x; } } return c != INF ? (int)c : (int)a; } }
- 时间复杂度：$O(n)$
- 空间复杂度：$O(1)$
其他
国庆题太简单？
不如来做一道热乎的 背包问题求方案数（公主号「背包专题」的第 $20$ 讲，共 $23$ 讲）🍭🍭🍭
或是加练如下「模拟」或「排序」题目 🍭🍭🍭
1. 模拟
注：以上目录整理来自 wiki，任何形式的转载引用请保留出处。
2. 排序
| 题目 | 题解 | 难度 | 推荐指数 |
|---|---|---|---|
| 41. 缺失的第一个正数 | LeetCode 题解链接 | 困难 | 🤩🤩🤩 |
| 220. 存在重复元素 III | LeetCode 题解链接 | 中等 | 🤩🤩🤩 |
| 414. 第三大的数 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 448. 找到所有数组中消失的数字 | LeetCode 题解链接 | 简单 | 🤩🤩🤩 |
| 524. 通过删除字母匹配到字典里最长单词 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 581. 最短无序连续子数组 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 611. 有效三角形的个数 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 645. 错误的集合 | LeetCode 题解链接 | 简单 | 🤩🤩🤩 |
| 703. 数据流中的第 K 大元素 | LeetCode 题解链接 | 简单 | 🤩🤩🤩 |
| 987. 二叉树的垂序遍历 | LeetCode 题解链接 | 困难 | 🤩🤩🤩🤩🤩 |
| 1833. 雪糕的最大数量 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩🤩 |
| 1834. 单线程 CPU | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 1838. 最高频元素的频数 | LeetCode 题解链接 | 中等 | 🤩🤩🤩 |
| 面试题 10.02. 变位词组 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 面试题 17.14. 最小K个数 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
注：以上目录整理来自 wiki，任何形式的转载引用请保留出处。
最后
如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ (“▔□▔)/
也欢迎你 关注我（公主号后台回复「送书」即可参与长期看题解学算法送实体书活动）或 加入「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。
所有题解已经加入 刷题指南，欢迎 star 哦 ~
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 92265 | 234170 | 39.4% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
相似题目
| 题目 | 难度 |
|---|---|
| 数组中的第K个最大元素 | 中等 |
