LeetCode 414. Third Maximum Number

Given an integer array nums, return the third distinct maximum number in this array. If the third maximum does not exist, return the maximum number.

Example 1:

Input: nums = [3,2,1]
Output: 1
Explanation:
The first distinct maximum is 3.
The second distinct maximum is 2.
The third distinct maximum is 1.

Example 2:

Input: nums = [1,2]
Output: 2
Explanation:
The first distinct maximum is 2.
The second distinct maximum is 1.
The third distinct maximum does not exist, so the maximum (2) is returned instead.

Example 3:

Input: nums = [2,2,3,1]
Output: 1
Explanation:
The first distinct maximum is 3.
The second distinct maximum is 2 (both 2's are counted together since they have the same value).
The third distinct maximum is 1.

Constraints:

• 1 <= nums.length <= 104
• -231 <= nums[i] <= 231 - 1

Follow up: Can you find an O(n) solution?

---

就是找一个数组中第三大的元素。注意题目的要求是如果有重复数字的话，只计算一次。并且如果没有第三大的元素的话，需要返回最大的元素。嗯，看起来很简单，用三个变量记录前三大的数字就行，但是提交了两次都被corner case坑死了，两个corner case分别是：

[-2147483648,1,1] -> 1
[1,2,-2147483648] -> -2147483648

首先注意是初始化这三个变量的时候，需要初始化为long或者直接用Integer（初始化为null），不能直接用int，不然就会出现-2147483648 == -2147483648的情况，就会以为它没有第三大的元素而返回最大的。嗯，然后就是初始化他们仨都为MIN_VALUE是可以的，不需要让他们不相等。

Runtime: 4 ms, faster than 77.75% of Java online submissions for Third Maximum Number.

Memory Usage: 43.1 MB, less than 79.24% of Java online submissions for Third Maximum Number.

class Solution {
    public int thirdMax(int[] nums) {
        long max = Long.MIN_VALUE;
        long secondMax = Long.MIN_VALUE;
        long thirdMax = Long.MIN_VALUE;
        
        for (int num : nums) {
            if (num == max || num == secondMax || num == thirdMax) {
                continue;
            }
            if (num >= max) {
                thirdMax = secondMax;
                secondMax = max;
                max = num;
            } else if (num >= secondMax && num < max) {
                thirdMax = secondMax;
                secondMax = num;
            } else if (num >= thirdMax && num < secondMax) {
                thirdMax = num;
            }
        }
        
        return thirdMax == Long.MIN_VALUE ? (int)max : (int)thirdMax;
    }
}

---

看了下solutions还有heap的解法，也是非常经典了呢。甚至有点忘了heap怎么做。这题我们要返回第三大的元素，于是要keep heap size为3，因为heap要返回的是top的元素，所以我们要返回这三个里最小的，于是需要用min heap。然后就是复习了一下heap的写法，返回top是peak()，remove掉top是poll()，加元素add()或者offer()，remove元素remove(E)。heap解法的套路就是遍历数组，如果heap size < k就无脑加，否则就heap.peek()和当前num比大小，此时minHeap就是如果num更大，就要heap.poll()然后加num。这题额外的因为最后要看是否存在第三大的元素，所以如果heap里有俩元素的话要先把top给poll掉再返回top。

Runtime: 10 ms, faster than 44.88% of Java online submissions for Third Maximum Number.

Memory Usage: 44.7 MB, less than 20.92% of Java online submissions for Third Maximum Number.

class Solution {
    public int thirdMax(int[] nums) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        
        for (int num : nums) {
            if (!minHeap.contains(num)) {
                if (minHeap.size() < 3) {
                    minHeap.add(num);
                } else if (minHeap.peek() < num) {
                    minHeap.poll();
                    minHeap.add(num);
                }
            }
        }
        
        if (minHeap.size() == 2) {
            minHeap.poll();
        }
        return minHeap.peek();
    }
}

---

还有用treeset的，嗯，这样可以避免前面用heap的时候两个麻烦之处：1. contains()的时间复杂度是O(1)，虽然heap时因为只有三个元素所以复杂度也可以忽略不计但还是会更好些；2. treeset既可以first()又可以last()，都能拿到，就很方便。那么问题来了，为什么其他用heap的题不用treeset呢？treeset和heap相比有什么overhead呢？看了一圈，感觉对于treeset的first()和last()的复杂度是O(1)还是O(logn)有点争议，但heap绝对是O(1)就对了。两个代码写起来几乎是一模一样的。

Runtime: 16 ms, faster than 23.03% of Java online submissions for Third Maximum Number.

Memory Usage: 44.4 MB, less than 28.67% of Java online submissions for Third Maximum Number.

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

TreeSet vs heap:

algorithm - Computational Complexity of TreeSet methods in Java - Stack Overflow

java - When should I use a TreeMap over a PriorityQueue and vice versa? - Stack Overflow