[Leetcode] Third Maximum Number

Given integer array nums, return the third 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 third maximum is 1.

 

Example 2:

Input: nums = [1,2]

Output: 2

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

 

Example 3:

Input: nums = [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.

 

Constraints:

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

Follow up: Can you find an O(n) solution?

 

 

[ 내 코드 ]

- O(n)으로 풀려고 많은 고민을 했는데, 결국 std::set를 이용해서 O(nlogn)으로 풀었다..

class Solution {
public:
    int thirdMax(vector<int>& nums)
    {
        set<int> s;
        for(int num : nums)
        {
            s.insert(num);
        }

        int maxVal = numeric_limits<int>::min();
        int cnt = 0;
        for(auto it = s.rbegin(); it != s.rend(); ++it)
        {
            cnt++;
            maxVal = std::max(maxVal, *it);
            if(cnt == 3) return *it;
        }

        return maxVal;
    }
};

 

수행속도 상위 코드는 그냥 정렬로 풀어져 있었고,

class Solution {
public:
    int thirdMax(vector<int>& nums) {
        int saveIndex = 0;
        int times = 0;
        sort(nums.begin(), nums.end(), std::greater<int>());
        for (int i = 0; i < nums.size() - 1; i++){
            if (nums[i] != nums[i + 1]){
                times++;
                }
            if (times == 2){
                saveIndex = i + 1;
                break;
                }
        }
        return nums[saveIndex];
    }
};

 

수행속도 최상위 코드는 봤는데, 그냥 쌩구현으로 풀었다.

class Solution {
public:
    int thirdMax(vector<int>& nums) {
        long first = LONG_MIN, second = LONG_MIN, third = LONG_MIN;
        
        for(auto const& x: nums){
            if(x != first && x!= second && x!= third){
                if(x > second){
                    if(x > first)
                        third = second, second = first, first = x;
                    else
                        third = second, second = x;
                }
                else{
                    if(x > third)
                        third = x;
                }
            }
        }
        
        if(third != LONG_MIN) return third;
        else return max(first, second);
    }
};