414 第三大的数

题目

给定一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。要求算法时间复杂度必须是O(n)。

示例 1:

输入: [3, 2, 1]

输出: 1

解释: 第三大的数是 1.

示例 2:

输入: [1, 2]

输出: 2

解释: 第三大的数不存在, 所以返回最大的数 2 .

示例 3:

输入: [2, 2, 3, 1]

输出: 1

解释: 注意，要求返回第三大的数，是指第三大且唯一出现的数。
存在两个值为2的数，它们都排第二。

题解

1. 一种解题思路是数组去重并排序，然后根据排好位置的数组取值即可

TIP

执行用时：92 ms, 在所有 JavaScript 提交中击败了 31.15% 的用户

内存消耗：39.8 MB, 在所有 JavaScript 提交中击败了 47.97% 的用户

/**
 * @param {number[]} nums
 * @return {number}
 */
var thirdMax = function(nums) {
    // 使用 Set 数据结构去重
    // 使用 sort 方法排序
    nums = [...new Set(nums)].sort((a, b) => b -a)
    // 判断如果 nums 的第三个有值的情况下
    // 直接返回即可，否则返回最大的值
    return nums[2] == undefined ? nums[0] : nums[2]
};

• 时间复杂度：O(n)，解构 Set 一次，使用 sort 排序一次。
• 空间复杂度：O(n)，使用 Set 进行储存。
• 最好情况：给定的数组大部分值是按从大到小的顺序，这样排序就不用花费太多的时间
• 最坏情况：给定的数组中所有值都为乱序，排序需要花费大部分时间

2. 另一种解题思路，是维护三个值，遍历一次数组，每次进行比较，然后动态的进行赋值。

TIP

执行用时：84 ms, 在所有 JavaScript 提交中击败了 54.68% 的用户

内存消耗：38.1 MB, 在所有 JavaScript 提交中击败了 89.43% 的用户

/**
 * @param {number[]} nums
 * @return {number}
 */
var thirdMax = function(nums) {
    let min = 0 // 最小值
    let middle = -Infinity  // 中间值
    let max = -Infinity  // 最大值

    for(let i=0,l=nums.length;i<l;i++) {
        let currentCount = nums[i] // 当前值

        // 如果当前值大于 max
        if(currentCount > max) {
            let tempMax = max // 储存 max
            let tempMiddle = middle // 储存 middle
            /**
             * 分别把 max 替换为当前值；
             * 中间值替换为 max
             * 最小值替换为中间值
            **/
            max = currentCount
            middle = tempMax
            min = tempMiddle
        }

        if(currentCount < max && currentCount > middle) {
            let tempMiddle = middle // 储存中间值
            /**
             * 中间值替换为当前值
             * 最小值替换为中间值
            **/
            middle = currentCount
            min = tempMiddle
        }

        if(currentCount < middle && currentCount > min) {
            /**
             * 直接替换为最小值
            **/
            min = currentCount
        }
    }

    /**
     * 如果 min 不等于 -Infinity，说明已经经过了三轮比较，所以返回 min 即可，否则返回 max
    **/ 
    if(min !== -Infinity) {
        return min
    }

    return max
};

• 时间复杂度：O(n)，通过一次 for 循环遍历。
• 空间复杂度：O(1)，应该属于常数级别，只创建了三个变量来储存。
• 最好情况：
• 最坏情况：