【Leetcode】414. Third Maximum Number

Description

Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).

Example

Input: [3, 2, 1]
Output: 1
Explanation: The third maximum is 1.

Solution

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

Result

AC

Analyse

这个方法很简洁，因为要判断nums[i]和nums[i - 1]的大小比较，但是在i-1的过程中担心i-1会超过左边界，所以count开始就算1，这样相当于把最大的那个数在for之前已经算了。后来看了几个别的算法，觉得我的算法是最好的。

First

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

Analyse

这个算法就是利用了Integer的空属性，但是写的时候要注意用equals而不是==。

Second

public int thirdMax(int[] nums) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        Set<Integer> set = new HashSet<>();
        for (int n : nums) {
            if (!set.contains(n)) {
                pq.add(n);
                set.add(n);
                if (pq.size() > 3) {
                    set.remove(pq.poll());
                }
            }
    
        if (pq.size() < 3) {
            while (pq.size() > 1) {
                pq.poll();
            }
        }
        return pq.peek();
    }

Analyse

利用了PriorityQueue的默认排序是增序，再加上一个HashSet进行重复性的判断，有个地方需要注意的是如果queue的size大于3，那么set也要把这个对应的数字也remove。