题目描述

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

示例 1：

输入：[3, 2, 1]
输出：1
解释：第三大的数是 1 。
示例 2：

输入：[1, 2]
输出：2
解释：第三大的数不存在, 所以返回最大的数 2 。
示例 3：

输入：[2, 2, 3, 1]
输出：1
解释：注意，要求返回第三大的数，是指在所有不同数字中排第三大的数。
此例中存在两个值为 2 的数，它们都排第二。在所有不同数字中排第三大的数为 1 。


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

思路分析

• 今天的算法题目是求解第三大的数，看到题目我们需要对数组进行排序，然后得到答案。

• 需要注意的是，求解第三大的数，需要对排序的数进行去重复，我们使用 set 进行去重。实现代码如下：

通过代码

class Solution {
    public int thirdMax(int[] nums) {
        Set set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        List list = new ArrayList<>(set);
        Collections.sort(list);
        int n = list.size();
        int ans = 0;
        if (n < 3) {
            ans = list.get(n - 1);
        } else {
            ans = list.get(n - 3);
        }

        return ans;
    }
}

总结

• 上述算法的时间复杂度是O(n log n), 空间复杂度是O(n)

• 坚持算法每日一题，加油！