[LeetCode]Ar414. 第三大的数

🚩传送门：https://leetcode-cn.com/problems/intersection-of-two-arrays/

题目

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

示例 1：

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

示例 2：

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

示例 3：

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

解题思路：指针模拟

定义 3 个指针， first , second ,third, 分别记录第一大，第二大，第三大元素

难点在于处理边界问题

注意： 这里的第几大，是绝对大， e.g. 1,2,2, 3第三大为 1, 而非 2

这里注意边界， 元素的个数时可能小于 3 个的。

• 一个元素，返回自身
• 二元素，取最大值即可

但代码那么写不大优雅，具体过程看代码

复杂度分析

时间复杂度：。

空间复杂度：。

官方代码

class Solution {
    public int thirdMax(int[] nums) {
        int len  = nums.length;
        // 长度小于等于 2 时，取最大值即可
        if (len <= 2) {
            return Math.max(nums[0], nums[len - 1]);
        }
        long first, second, third;
        // 取最小值
        first = second = third = Long.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int cur = nums[i];
            // 由于第几大都是不能重复的，也就是说当前元素 cur 如果等于 first, second 时，忽略即可
            if (cur == first || cur == second) {
                // 忽略当前元素
                continue;
            }
            if (cur > first) {
                third = second;
                second = first;
                first = cur;
                continue;
            }
            if (cur > second) {
                third = second;
                second = cur;
                continue;
            }
            if (cur > third) {
                third = cur;
            }
        }
        return third == Long.MIN_VALUE ? (int)first : (int)third;
    }
}