[数据结构与算法]LeetCode-每日一题 414. 第三大的数 [Java实现] [极速]

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

示例 1：

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

示例 2：

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

方法一：直接求解 (O(n))?

????????因为进阶解法要求时间复杂度O(n)，?故我们抛弃排序除重直接用一遍遍历求解。具体做法为定义三个变量，在每次遍历时根据所给数据大小对其进行更新。因为题目给定的为int数组，故我们用long型变量储存临界值便于结果判断。

    private long first = Long.MIN_VALUE;
    private long second = first;
    private long third = second;

    public int thirdMax(int[] nums) {
//        Arrays.sort(nums);
        for (int i = nums.length-1; i >= 0; -- i) {
            int correct = nums[i];
            if (i > 0 && correct == nums[i-1]) continue;
            if (correct == first || correct == second) continue;
            if (correct > first) {
               third = second;
               second = first;
               first = correct;
            } else if (correct > second) {
                third = second;
                second = correct;
            } else if (correct > third) {
                third = correct;
            }
        }
        return (int) (third == Long.MIN_VALUE ? first : third);
    }

?????????????????????????????????????????????????????