每日一题：每天一个新挑战；
循序渐进：从易到难，扎实掌握；
系统分类：按数据结构分类，有助于构建知识框架；
丰富题量：100 道精选题，覆盖简单/中等/困难难度。

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

示例 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，说明没有第三大的数，返回数组中的最大数。
如果去重后的数组长度大于或等于 3，返回数组中第三大的数。

时间复杂度: O(n log n)，排序过程占主要时间复杂度。
空间复杂度: O(n)，去重后的数组占用额外空间。

var thirdMax = function(nums) {
    nums = [...new Set(nums)];
    nums.sort((a, b) => b - a);
    return nums.length >= 3 ? nums[2] : nums[0];
};

方法二：三指针法

通过三指针的方法找出数组中最大的三个数。
初始化三个指针为 first = -Infinity, second = -Infinity, third = -Infinity。
遍历数组，对于每个数：

如果该数大于 first，则将 first 更新为该数，并将 second 和 third 依次后移。
如果该数介于 second 和 first 之间，更新 second，并将 third 后移。
如果该数介于 third 和 second 之间，更新 third。

如果 third 仍然是 -Infinity，说明不存在第三大的数，返回 first；否则返回 third。

时间复杂度: O(n)，只需遍历一次数组。
空间复杂度: O(1)，仅使用常数空间。

var thirdMax = function(nums) {
    let first = -Infinity, second = -Infinity, third = -Infinity;
    for (let num of nums) {
        if (num > first) {
            third = second;
            second = first;
            first = num;
        } else if (num > second && num < first) {
            third = second;
            second = num;
        } else if (num > third && num < second) {
            third = num;
        }
    }
    return third === -Infinity ? first : third;
};