414-第三大的数.md

414-第三大的数

题目信息

题目地址： 414. 第三大的数

题目内容：

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

示例 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)的解决方案吗？

题解

解法一

思路：

考虑到输入数组中可能存在重复的数字，所以需要先去重。然后将数组按照从大到小的顺序排序

判断数组长度，如果长度小于3，则返回数组中的最大值，否则返回数组中下标为2的元素

代码实现：

/**
 * @param {number[]} nums
 * @return {number}
 */
var thirdMax = function(nums) {
    const map = new Map()
    nums = nums.filter(i => !map.get(i) && map.set(i, true)).sort((a, b) => b - a)
    return nums.length < 3 ? nums[0] : nums[2]
};

去重也可以使用Set：

/**
 * @param {number[]} nums
 * @return {number}
 */
var thirdMax = function(nums) {
    let arr = new Set(nums)
    arr = [...arr].sort((a, b) => b - a)
    return arr.length < 3 ? arr[0] : arr[2]
};

解法二

思路：

和628-三个数的最大乘积的方法二类似，算出数组中最大的三个数

但是需要注意，数组中可能有重复的数，比较时需要兼容一下

代码实现：

/**
 * @param {number[]} nums
 * @return {number}
 */
var thirdMax = function(nums) {
    let max1 = -Infinity,
        max2 = -Infinity,
        max3 = -Infinity
    for(const num of nums) {
        if(num > max1) {
            max3 = max2
            max2 = max1
            max1 = num
        }else if(num > max2 && max1 > num) {
            max3 = max2
            max2 = num
        }else if(num > max3 && max2 > num) {
            max3 = num
        }
    }
    return max3 === -Infinity ? max1 : max3
};