動機

heapq是不是比較慢啊

Problem

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: 1Explanation: The third maximum is 1.

Example 2:

Input: nums = [1,2]Output: 2Explanation: The third maximum does not exist, so the maximum (2) is returned instead.

Example 3:

Input: nums = [2,2,3,1]Output: 1Explanation: 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?

Sol

用heapq排序

class Solution:
    def thirdMax(self, nums: List[int]) -> int:
        maxs = []
        nums = list(set(nums))
        for n in nums:
            heappush(maxs,n)
            if len(maxs) > 3:
                heappop(maxs)
            print(maxs)
        return min(maxs) if len(maxs) == 3 else max(maxs)

無腦一點用sort

class Solution:
    def thirdMax(self, nums: List[int]) -> int:
        nums = list(set(nums))
        nums.sort(reverse=True)
        if len(nums) < 3:
            return nums[0]
        else:
            return nums[2]