動機
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]