内容

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

示例 1:

输入: [3, 2, 1]

输出: 1

解释: 第三大的数是 1.
示例 2:

输入: [1, 2]

输出: 2

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

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

输出: 1

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

思路

声明三个变量，分别表示第一大，第二大，第三大的数，每次循环遍历时候判断，如果大于第一大，那么第一大移位到第二大，第二大移位到第三大依次类推。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var thirdMax = function(nums) {
    var min=-(Math.pow(2,31)+100)
    var max1=min;
    var max2=min;
    var max3=min;
    
    for(var i=0;i<nums.length;i++){
        var val=nums[i];
        if(val ==max1||val ==max2||val ==max3){
            continue;
        }
        
        if(val>max1){
            max3=max2;
            max2=max1;
            max1=val;
        }else if(val>max2){
            max3=max2;
            max2=val;
        }else if(val>max3){
            max3=val;
        }
    }
    return max3==min?max1:max3;
};

回到目录