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).

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

Output: 1

Explanation: The third maximum is 1.
1
2
3
4
5
6
Example 2:
Input: [1, 2]

Output: 2

Explanation: The third maximum does not exist, so the maximum (2) is returned instead.
1
2
3
4
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.

Method

先将数组进行排序，排序的复杂度是O(n)。然后从大数开始往Set里面加，当Set的长度为3时，返回这个数。如果没有长度为3的情况，则返回最大的数。

Solution

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    public int thirdMax(int[] nums) {
        Arrays.sort(nums);
        Set<Integer> set = new HashSet<Integer>();
        for(int i = nums.length-1; i >= 0; i--){
            if(!set.contains(nums[i])) set.add(nums[i]);
            if(set.size() == 3) return nums[i];
        }
        return nums[nums.length-1];
    }
}