414. Third Maximum Number

题目：

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 1:

Input: [3, 2, 1]

Output: 1

Explanation: The third maximum is 1.

Example 2:

Input: [1, 2]

Output: 2

Explanation: The third maximum does not exist, so the maximum (2) is returned instead.

Example 3:

Input: [2, 2, 3, 1]

Output: 1

Explanation: Note that the third maximum here means the third maximum distinct number.
Both numbers with value 2 are both considered as second maximum.

链接：https://leetcode.com/problems/third-maximum-number/#/description

3/24/2017

performance 12%

注意的问题：

1. 第3行的初始化initialCapacity完全没有用，甚至对performance不好，可以设为nums.length

2. 第3行的comparator很有用，题中我们需要建立max heap，所以需要Collections.reverseOrder()

3. 第6行可以改为pq.contains()，但是performance大大下降，原因是linear time，而set是constant time

 1 public class Solution {
 2     public int thirdMax(int[] nums) {
 3         PriorityQueue<Integer> pq = new PriorityQueue<Integer>(3, Collections.reverseOrder());
 4         Set<Integer> s = new HashSet<Integer>();
 5         for (int i = 0; i < nums.length; i++) {
 6             if (s.contains(nums[i])) continue;
 7             s.add(nums[i]);
 8             pq.offer(nums[i]);
 9         }
10         if (pq.size() < 3) return pq.peek();
11         pq.poll();
12         pq.poll();
13         return pq.poll();
14     }
15 }

这道题当然有简单的做法，用3个变量即可。但是刷题时候多了解不熟悉的语言语法是很有必要的。

讨论中有人用c++的Set来做，原因是C++中set可以是ordered，占语言便宜啊哈哈

别人有对length的提高：每当多于3个时就删，是个好办法。非常像昨天的那道palindrome

 1 public class Solution {
 2     public int thirdMax(int[] nums) {
 3         PriorityQueue<Integer> pq = new PriorityQueue<>();
 4         Set<Integer> set = new HashSet<>();
 5         for (int i : nums) {
 6             if (!set.contains(i)) {
 7                 pq.offer(i);
 8                 set.add(i);
 9                 if (pq.size() > 3) {
10                     set.remove(pq.poll());
11                 }
12             }
13         }
14         if (pq.size() < 3) {
15             while (pq.size() > 1) {
16                 pq.poll();
17             }
18         }
19         return pq.peek();
20     }
21 }