LeetCode 414. Third Maximum Number 解題紀錄
題目
Given an integer array nums
, return the third distinct maximum number in this array. If the third maximum does not exist, return the maximum number.
Example 1:
Input: nums = [3,2,1]
Output: 1
Explanation:
The first distinct maximum is 3. The second distinct maximum is 2. The third distinct maximum is 1.
Example 2:
Input: nums = [1,2]
Output: 2
Explanation:
The first distinct maximum is 2. The second distinct maximum is 1. The third distinct maximum does not exist, so the maximum (2) is returned instead.
Example 3:
Input: nums = [2,2,3,1]
Output: 1
Explanation: The first distinct maximum is 3. The second distinct maximum is 2 (both 2’s are counted together since they have the same value). The third distinct maximum is 1.
Constraints:
- 1 $\leq$ nums.length $\leq 10^4$
- $-2^{31} \leq$ nums[i] $\leq 2^{31} - 1$
Follow up: Can you find an $O(n)$ solution?
想法
將 nums
中所有元素進行排序,排序後剔除重複的元素。
若 nums.size$\geq$3 則取得倒數第三大的元素,反之則取最後一個元素(最大的)。
解法
解法一
用 vector 實作
int thirdMax(vector<int>& nums) {
// 排序所有元素
sort(nums.begin(), nums.end());
// ans 放置 nums 中不重複值的元素
vector<int> ans;
int former = INT_MAX;
for(auto i:nums)
{
if(i != former)
{
ans.push_back(i);
}
former = i;
}
return ans.size()<3 ? ans[ans.size()-1] : ans[ans.size()-3];
}
- Time complexity: $\mathcal{O}(n)$.
- Space complexity: $\mathcal{O}(n)$.
解法二
既然要排序又希望 vector 中的元素唯一,那我們應該可以用 set 來實作吧?
int thirdMax(vector<int>& nums) {
set<int> top3;
for(auto i:nums)
{
top3.insert(i);
// 大於三個元素,捨棄最小的元素
if(top3.size()>3)
{
top3.erase(top3.begin());
}
}
// top3.begin(): 倒數第三大
// top3.rbegin(): 倒數第一大 / 最大
return top3.size()==3 ? *top3.begin() : *top3.rbegin();
}
- Time complexity: $\mathcal{O}(nlog(3))$.
- Space complexity: $\mathcal{O}(n)$.