README.md

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.

Solutions (Rust)

1. Solution

impl Solution {
    pub fn third_max(nums: Vec<i32>) -> i32 {
        let mut max_nums = Vec::new();
        for n in nums {
            if !max_nums.contains(&n) {
                match max_nums.len() {
                    0 => max_nums.push(n),
                    1 => {
                        if max_nums[0] < n {
                            max_nums.push(n);
                        } else {
                            max_nums.insert(0, n);
                        }
                    },
                    2 => {
                        if max_nums[1] < n {
                            max_nums.push(n);
                        } else if max_nums[0] > n {
                            max_nums.insert(0, n);
                        } else {
                            max_nums.insert(1, n);
                        }
                    },
                    3 => {
                        if max_nums[2] < n {
                            max_nums.push(n);
                            max_nums.remove(0);
                        } else if max_nums[1] < n {
                            max_nums.insert(2, n);
                            max_nums.remove(0);
                        } else if max_nums[0] < n {
                            max_nums.insert(1, n);
                            max_nums.remove(0);
                        }
                    },
                    _ => (),
                };
            }
        }
        if max_nums.len() < 3 {
            *max_nums.last().unwrap()
        } else {
            *max_nums.first().unwrap()
        }
    }
}