第三大的数

题目

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

示例 1:

输入: [3, 2, 1]

输出: 1

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

输入: [1, 2]

输出: 2

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

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

输出: 1

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/third-maximum-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

• 题目要求O(n)的时间复杂度,所以不能存在单次循环.可以设置三个量表示前三位数,循环时替代即可.

代码

第一遍的代码

class Solution {
    public int thirdMax(int[] nums) {
        //有复杂度要求,所以不能有嵌套循环
        if(nums.length == 1){
            return nums[0];
        }
        if(nums.length == 2){
            return Math.max(nums[0],nums[1]);
        }
        int max = nums[0];
        int sed = nums[0];
        int third = nums[0];
        for(int i = 1;i < nums.length;i++){
            if(nums[i] == max){
                continue;
            }
            if(nums[i] > max){
                if (third < sed){
                    third = sed;
                }
                if (sed < max){
                    sed = max;
                }
                max = nums[i];
                continue;
            }
            if(nums[i] < max){
                if(nums[i] == sed){
                    continue;
                }
                if(nums[i] > sed){
                    if (third < sed){
                        third = sed;
                    }
                    sed = nums[i];
                    continue;
                }
                if(nums[i] < sed){
                    if(nums[i] == third){
                        continue;
                    }
                    if(nums[i] > third || third == sed){
                        third = nums[i];
                    }
                    if (max == sed){
                        sed = third;
                        third = nums[i];
                    }
                }
            }
        }
        if(max == sed || sed == third){
            return max;
        }
        return third;
    }
}

下附好看一些的代码,效率是同上的

class Solution{
    /**
     * 1.About Complexity
     *     1.1 Time Complexity is O(n)
     *     1.2 Space Complexity is O(1)
     * 2.how I solve
     *     2.1 define three integer to cache three biggest number
     *     2.2 circulate from head to tail,there have 4 condition
     *             2.2.1 max1==nums[i]||max2==nums[i]||max3==nums[i],it means that there have repeating element in array,so I ignore it directly
     *             2.2.2 nums[i]>max3&&nums[i]>max1,transfer value from max1 to max3 in turn
     *             2.2.3 nums[i]>max3&&nums[i]>max2,tranfer value from max2 to max3
     *             2.2.4 nums[i]>max3,put current element to max3
     *     2.3 judge max3 value and returns the corresponding value
     * 3.About submit record
     *     3.1 2ms and 36.9MB memory in LeetCode China
     *     3.2 1ms and 36.1MB memory in LeetCode
     * 4.Q&A
     * @param nums
     * @return
     */
    public int thirdMax(int[] nums) {
        if(nums==null){
            return 0;
        }
        if(nums.length<2){
            return nums[0];
        }
        long max1=Long.MIN_VALUE,max2=Long.MIN_VALUE,max3=Long.MIN_VALUE;
        for(int i=0,length=nums.length;i<length;i++){
            if(max1==nums[i]||max2==nums[i]||max3==nums[i]){
                continue;
            }
            if(nums[i]>max3){
                if(nums[i]>max1){
                    max3=max2;
                    max2=max1;
                    max1=nums[i];
                }
                else{
                    if(nums[i]>max2){
                        max3=max2;
                        max2=nums[i];
                    }
                    else{
                        max3=nums[i];
                    }
                }
            }
        }
        System.out.print(max1+" "+max2+" "+max3);
        if(max3==Long.MIN_VALUE){
            return (int)max1;
        }
        else{
            return (int)max3;
        }
    }
}