【刷穿 LeetCode】414. 第三大的数 : 「排序」&「遍历」

题目描述

这是 LeetCode 上的 414. 第三大的数 ，难度为 简单。

Tag : 「排序」、「数组」、「模拟」

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 1 <= nums.length <= 10^4104
• -2^{31}−231 <= nums[i] <= 2^{31} - 1231−1

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

Set 去重 + 排序

题目要求返回含重复元素的数组 numsnums 中的第三大数。

一个朴素的做法是，先使用 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)；排序复杂度为 O(n\log{n})O(nlogn)。整体复杂度为 O(n\log{n})O(nlogn)
• 空间复杂度：O(n)O(n)

有限变量 + 遍历

经典的找数组次大值的做法是使用两个变量 a 和 b 分别存储遍历过程中的最大值和次大值。

假设当前遍历到的元素为 xx，当满足如下条件时，考虑更新 a 或者 b:

1. 当 x > ax>a 时，说明最大值被更新，同时原来的最大值沦为次大值。即有 b = a; a = x;b=a;a=x;
2. 在条件11不满足，且有x > bx>b时，此时可以根据是否有「严格次大值」的要求，而决定是否要增加x < ax<a的条件：

• 不要求为「严格次大值」：直接使用 xx 来更新 b，即有 b = xb=x；
• 当要求为「严格次大值」： 此时需要满足 x < ax<a 的条件，才能更新 b。

回到本题，同理我们可以使用 a、b 和 c 三个变量来代指「最大值」、「严格次大值」和「严格第三大值」。

从前往后遍历 numsnums，假设当前元素为 xx，对是否更新三者进行分情况讨论（判断优先级从上往下）：

1. x > ax>a，说明最大值被更新，将原本的「最大值」和「次大值」往后顺延为「次大值」和「第三大值」，并用 xx 更新 a；
2. x < ax<a 且 x > bx>b，说明次大值被更新，将原本的「次大值」往后顺延为「第三大值」，并用 xx 更新 b；
3. x < bx<b 且 x > cx>c，说明第三大值被更新，使用 xx 更新 c。

起始时，我们希望使用一个足够小的数来初始化 a、b 和 c，但由于 num[i]num[i] 的范围为 [-2^{31}, 2^{31} - 1][−231,231−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(n)
• 空间复杂度：O(1)O(1)

最后

这是我们「刷穿 LeetCode」系列文章的第 No.414 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。