414. Third Maximum Number

414. 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?

 

Solution 나의 코드 [Runtime:  48ms, Memory Usage:  15.4MB]

[Runtime beats 88.59% of python 3 submission] [Memory usage beats 42.51% of python3 submission]

class Solution:
    def thirdMax(self, nums: List[int]) -> int:
        if len(nums) < 3 or len(set(nums)) < 3:
            return max(nums)
        
        set_array = list(set(nums))
        for i in range(2):
            set_array.pop(set_array.index(max(set_array)))
        
        return max(set_array)

조금 정리한 버전

class Solution:
    def thirdMax(self, nums: List[int]) -> int:
        
        set_array = list(set(nums))
        if len(set_array) < 3:
            return max(set_array)
        
        for i in range(2):
            set_array.pop(set_array.index(max(set_array)))
        
        return max(set_array)

 

 

Solution 나의 코드2 [Runtime:  56ms, Memory Usage:  15.5MB]

[Runtime beats 43.33% of python 3 submission] [Memory usage beats 42.51% of python3 submission]

class Solution:
    def thirdMax(self, nums: List[int]) -> int:
        nums = set(nums)
        if len(nums) < 3:
            return max(nums)
        nums.remove(max(nums))
        nums.remove(max(nums))
        return max(nums)

 

 

* 확실히 pop()이 remove()함수보다 런타임 시간이 빠르다.