【LeetCode-414】第三大的数

6.9 第三大的数【414】

6.9.1 题目描述

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

6.9.2 方法一：排序

将数组从大到小排序后，从头开始遍历数组，通过判断相邻元素是否不同，来统计不同元素的个数。如果能找到三个不同的元素，就返回第三大的元素，否则返回最大的元素。

class Solution {
    
    public int thirdMax(int[] nums) {
    
        Arrays.sort(nums);
        reverse(nums);
        for (int i = 1, diff = 1; i < nums.length; ++i) {
    
            if (nums[i] != nums[i - 1] && ++diff == 3) {
     // 此时 nums[i] 就是第三大的数
                return nums[i];
            }
        }
        return nums[0];
    }

    public void reverse(int[] nums) {
    
        int left = 0, right = nums.length - 1;
        while (left < right) {
    
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }
}

复杂度分析

• 时间复杂度：O(nlogn)，其中 nn 是数组 nums 的长度。排序需要 O(nlogn) 的时间。
• 空间复杂度：O(logn)。排序需要的栈空间为 O(logn)。

6.9.3 方法二：有序集合

我们可以遍历数组，同时用一个有序集合来维护数组中前三大的数。具体做法是每遍历一个数，就将其插入有序集合，若有序集合的大小超过 3，就删除集合中的最小元素。这样可以保证有序集合的大小至多为 3，且遍历结束后，若有序集合的大小为 3，其最小值就是数组中第三大的数；若有序集合的大小不足 3，那么就返回有序集合中的最大值。

class Solution {
    
    public int thirdMax(int[] nums) {
    
        TreeSet<Integer> s = new TreeSet<Integer>();
        for (int num : nums) {
    
            s.add(num);
            if (s.size() > 3) {
    
                s.remove(s.first());
            }
        }
        return s.size() == 3 ? s.first() : s.last();
    }
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组 nums 的长度。由于有序集合的大小至多为 3，插入和删除的时间复杂度可以视作是 O(1) 的，因此时间复杂度为 O(n)。
• 空间复杂度：O(1)。

6.9.4 方法三：一次遍历

class Solution {
    
    public int thirdMax(int[] nums) {
    
        long a = Long.MIN_VALUE, b = Long.MIN_VALUE, c = Long.MIN_VALUE;
        for (long num : nums) {
    
            if (num > a) {
    
                c = b;
                b = a;
                a = num;
            } else if (a > num && num > b) {
    
                c = b;
                b = num;
            } else if (b > num && num > c) {
    
                c = num;
            }
        }
        return c == Long.MIN_VALUE ? (int) a : (int) c;
    }
}

另一种不依赖元素范围的做法是，将 aa、bb 和 cc 初始化为空指针或空对象，视作「无穷小」，并在比较大小前先判断是否为空指针或空对象。遍历结束后，若 cc 为空，则说明第三大的数不存在，返回 aa，否则返回 cc。

class Solution {
    
    public int thirdMax(int[] nums) {
    
        Integer a = null, b = null, c = null;
        for (int num : nums) {
    
            if (a == null || num > a) {
    
                c = b;
                b = a;
                a = num;
            } else if (a > num && (b == null || num > b)) {
    
                c = b;
                b = num;
            } else if (b != null && b > num && (c == null || num > c)) {
    
                c = num;
            }
        }
        return c == null ? a : c;
    }
}

复杂度分析

• 时间复杂度：O(n)，其中 nn 是数组 nums 的长度。
• 空间复杂度：O(1)。

6.9.5 my answer—排序

class Solution {
    
    public int thirdMax(int[] nums) {
    
        Arrays.sort(nums);
        int count = 1;
        for (int i = nums.length - 2; i >= 0; i--) {
    
            if(nums[i]!=nums[i+1])count++;
            if (count==3)return nums[i];
        }
        return nums[nums.length-1];
    }
}