414. Third Maximum Number
1. 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).
2. Example
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.
3. Solutions
My Accepted Solution
n = i_nums.size()
Time complexity: O(n)
Space complexity: O(1)
class Solution
{
public:
// int thirdMax(vector<int>& nums)
int thirdMax(vector<int> &i_nums)
{
vector<int> maxValues; // we could also use a heap with the capacity of 3, or a set
for(int i = 0; i < i_nums.size(); i++)
{
if(find(maxValues.begin(), maxValues.end(), i_nums[i]) == maxValues.end())
{
maxValues.push_back(i_nums[i]);
sort(maxValues.begin(), maxValues.end(), [](int left, int right){return left > right;});
if(maxValues.size() > 3) maxValues.pop_back();
}
}
return (maxValues.size() == 3 ? maxValues.back() : maxValues.front());
}
};