leetcode [#414]

目录

• 1. 题目
• 2. 解决方案
• 3. 注意事项

题目

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

Example1:
Input: [3, 2, 1]

Output: 1

Explanation: The third maximum is 1.

Example2:
Input: [1, 2]

Output: 2

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

Example3:
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.

---

解决方案

public class Solution {
    public int thirdMax(int[] nums) {
        int N = nums.length;
        Set<Integer> set = new TreeSet<>();
        for(int i = 0; i < N; i++){
            set.add(nums[i]);
        }
        List<Integer> list = new LinkedList<>(set);
        if(list.size() < 3){
            return list.get(list.size() - 1);
        } else {
            return list.get(list.size() - 3);
        }
    }
}

---

注意事项

1. 使用TreeSet，结果有序且可以去重。之后取出相应元素即可。