414. 第三大的数

414. 第三大的数

一、题目描述：

给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数。 示例 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) 的解决方案吗？ 来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/third-maximum-number 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、思路分析：

这道题考察了什么思想？你的思路是什么？

看到这道题目我又真的这就是一道要解出来很简单的题目，但是要达到时间复杂度或空间复杂度很小的情况却不是那么容易做到的，比如此题你能设计一个时间复杂度 O(n) 的解决方案吗？

我的思路还是比较简单的，首先判断数组长度是否大于等于三，如果小于三，将数组排序后，直接返回最后一个元素即可，如果大于或等于三的话，我们就建立一个集合，然后将排序后的数组从尾到头遍历，放入三个不重复的数字到集合m中，如果集合m的长度等于三时，我们就返回该值。

下面尝试一下！

做题的时候是不是一次通过的，遇到了什么问题，需要注意什么细节？

是一次通过的！这道题目主要是要有思路，有思路解题起来就十分容易！

有几种解法，哪种解法时间复杂度最低，哪种解法空间复杂度最低，最优解法是什么？其他人的题解是什么，谁的效率更好一些？用不同语言实现的话，哪个语言速度最快？

理清思路，需要三个变量来存放最大的三个数，从头开始遍历，把当前数分别按顺序与三个数进行比较，最大的放在第一个，第二大的放在第二个，第三大的放在第三个。结束时，如果第三个数有值则返回，没有则返回第一个数。贴一个java版本供大家参考。这是按照题意的思路来的，还是比较耗时的，大家有好的欢迎讨论呀。

class Solution {
    public int thirdMax(int[] nums) {
        Integer max1 = null;
        Integer max2 = null;
        Integer max3 = null;
        for (Integer x : nums) {
            if (x.equals(max1) || x.equals(max2) || x.equals(max3)) {
                continue;
            }
            if ((max1 == null) || x > max1) {
                max3 = max2;
                max2 = max1;
                max1 = x;
            }
            else if ((max2 == null) || x > max2) {
                max3 = max2;
                max2 = x;
            }
            else if ((max3 == null) || x > max3) {
                max3 = x;
            }
        }
        if (max3 == null) {
            return max1;
        }else {
            return max3;
        }
    }
}

三、AC 代码：

func thirdMax(nums []int) int {
    sort.Ints(nums)
    length := len(nums)
    if length < 3 {
        return nums[length-1]
    }else {
        m := make(map[int]int)
        for i:= length-1;i>=0;i--{
            m[nums[i]] = nums[i]
            if len(m) == 3{
                return nums[i]
            }
        }
    }
    return nums[length-1]
}

四、总结：

难得通过前面的学习考虑到一次遍历解决的方法, 之前一直采用int类型记录最值,对于测试用例中[1, 2, INT_MIN]类型的用例很难去判断究竟返回最大值还是第三大，看答案发现居然用long类型，用这种方式去避免判断不如删掉这个用例