Given a non-empty array, return the third-largest number in the array. If it does not exist, return the largest number in the array.

Example 1:

Input:[3, 2, 1]
Output:1
Explanation:The third-largest number is 1.

Example 2:

Input:[1, 2]
Output:2
Explanation:The third-largest number does not exist, so return the largest number, 2.

Example 3:

Input:[2, 2, 3, 1]
Output:1
Explanation:Remember that the third-largest number means the third-largest number among all distinct values.
There are two values equal to 2, and both rank second. The third-largest distinct value is 1.

Constraints:

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

Follow-up: Can you design a solution with O(n) time complexity?

Analysis

#

For this type of problem, a sorted array is usually enough.

For an O(n) solution, maintain a sorted array whose size never exceeds three, because any additional elements are not needed.

Rust Code

#

# struct Solution;
use std::collections::BTreeSet;
impl Solution {
    pub fn third_max(mut nums: Vec<i32>) -> i32 {
        let mut set = BTreeSet::new();
        for item in nums {
            set.insert(item);
        }
        *set.iter().rev().nth(2).unwrap_or(set.iter().last().unwrap())
    }
}