leetcode 414 Third Maximum Number
z
 2019-04-12 09:31:51  

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:

1
2
3
4
5
Input: [3, 2, 1]

Output: 1

Explanation: The third maximum is 1.

Example 2:

1
2
3
4
5
Input: [1, 2]

Output: 2

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

Example 3:

1
2
3
4
5
6
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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    public int thirdMax(int[] nums) {
        if (nums.length == 0)
            return 0;
        if (nums.length == 1)
            return nums[1];
        if (nums.length == 2)
            return Math.max(nums[0], nums[1]);
        
        Integer a = null;
        Integer b = null;
        Integer c = null;
        
        for (int i=0; i<nums.length; i++) {
            Integer d = nums[i];
            
            if (d.equals(a) || d.equals(b) || d.equals(c))
                continue;
            if (a == null || d > a) {
                c = b;
                b = a;
                a = d;
            }
            else if ( b == null || d > b) {
                c = b;
                b = d;
            }
            else if (c == null || d > c) {
                c = d;
            }

        }
        return c==null?a: c;
    }
}