LeetCode414、第三大的数

题目描述

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

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

提示： 1 <= nums.length <= 10(4) -2(31) <= nums[i] <= 2(31)1

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

题目解析

题目在说什么

这道题想让你从一个数组里找出“第三大的数”。注意，这里说的“第三大”是指所有不同的数字里排第三大的。如果不同的数字不够三个，那就返回最大的那个数。

比如：

• 数组是 [3, 2, 1]，不同的数字有 3、2、1，第三大就是 1。
• 数组是 [1, 2]，不同的数字只有两个，不够三个，那就返回最大的数 2。
• 数组是 [2, 2, 3, 1]，虽然有两个 2，但只算一个不同的数字，所以不同的数字是 2、3、1，第三大是 1。

简单说就是：先去掉重复的数字，然后看剩下的个数，如果 >=3，就返回第三大的；如果 <3，就返回最大的。

思路是怎么来的

想象一下，你面前有一堆写着数字的卡片，你要找出第三大的那个数字（不能重复算）。你会怎么做？

最直接的办法：先把所有不同的数字挑出来，然后从大到小排个序，第三个就是答案。如果不同的数字不够三个，那就直接找最大的。

这个方法很直观，但排序需要花时间。题目要求更快的办法，时间复杂度 O(n)，意思就是只遍历数组一遍左右就能搞定。

那怎么不排序也能找到第三大的呢？我们可以用“三个变量”来记录当前看到的最大的三个数。就像你参加比赛，只记前三名的成绩，每次看到一个新成绩，就看看能不能挤进前三，把原来的名次往后推。

比如一开始前三名是空的，你看到第一个数 5，它就是第一名。看到第二个数 3，它比 5 小，所以是第二名。看到第三个数 7，它比 5 大，所以 5 变成第二名，7 变成第一名。这样一直更新，最后第三名就是我们要的答案。

但要注意：重复的数字不能算，所以如果看到和第一名、第二名一样的数，就跳过。

代码逐步拆解

我们来看参考代码，一行一行讲清楚。

Set<Integer> uniqueNums = new HashSet<>();
for (int num : nums) {
    uniqueNums.add(num);
}

这步是去重。HashSet 就像一个盒子，你往里放数字，重复的放不进去。这样 uniqueNums 里就只有不同的数字了。

List<Integer> numsNoRepeat = new ArrayList<>(uniqueNums);

把去重后的数字转成列表，方便后面操作。

if (numsNoRepeat.size() < 3) {
    int max = Integer.MIN_VALUE;
    for (int num : nums) {
        max = Math.max(max, num);
    }
    return max;
}

如果不同的数字少于三个，那就直接返回原数组的最大值。Integer.MIN_VALUE 是整数的最小值，用来初始化 max，然后遍历所有数字，不断更新 max 为更大的数。

Collections.sort(numsNoRepeat, Collections.reverseOrder());

如果不同的数字 >=3，那就先给它们排个序，从大到小。Collections.reverseOrder() 表示降序。

int first = numsNoRepeat.get(0);
int second = numsNoRepeat.get(1);
int third = numsNoRepeat.get(2);

取前三个作为初始的第一、第二、第三大。

for (int i = 3; i < numsNoRepeat.size(); i++) {
    int num = numsNoRepeat.get(i);
    if (num > first) {
        third = second;
        second = first;
        first = num;
    } else if (second < num && num < first) {
        third = second;