Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).
Example 1:
Input: [3, 2, 1]
Output: 1
Explanation: The third maximum is 1.
Example 2:
Input: [1, 2]
Output: 2
Explanation: The third maximum does not exist, so the maximum (2) is returned instead.
Example 3:
Input: [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.
思路：
- 先通过归并排序把数组有序化，然后除去数组中重复的元素，最后拿到第三大的元素。
- Python中有个collections模块，它提供了个类Counter，用来跟踪值出现了多少次。注意key的出现顺序是根据计数的从大到小。它的一个方法most_common(n)返回一个list, list中包含Counter对象中出现最多前n个元素。
- heapq模块有两个函数：nlargest() 和 nsmallest() 可以从一个集合中获取最大或最小的N个元素列表。heapq.nlargest (n, heap) #查询堆中的最大元素，n表示查询元素个数
def thirdMax3(self, nums):
import heapq
return heapq.nlargest(3, set(nums))[2 if len(set(nums))>2 else 0]
def thirdMax4(self, nums):
nums = sorted(list(set(nums)))
if len(nums)<3:
return max(nums)
else:
return nums[-3]
其他人的解法：
把数组中重复的元素通过set去掉，然后remove掉两次最大值，在整下的元素里面取最大值，就是第三大值。
取一个数组放入三个最小值元素，然后依次从nums中取值和这三个值比较， 如果比哪个值大，就放在对应的位置。如果最小值元素还在数组里面，就返回最大值，否则就返回第三个元素(也即是第三大元素)
#!/usr/bin/env python
# -*- coding: UTF-8 -*-
class Solution(object):
def thirdMax(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) <= 2:
return max(nums)
nums = set(nums)
nums.remove(max(nums))
nums.remove(max(nums))
return max(nums)
def thirdMax2(self, nums):
v = [float('-inf'), float('-inf'), float('-inf')]
for num in nums:
if num not in v:
if num > v[0]:
v = [num, v[0], v[1]]
print v
elif num > v[1]:
v = [v[0], num, v[1]]
print v
elif num > v[2]:
v = [v[0], v[1], num]
print v
return max(nums) if float('-inf') in v else v[2]
if __name__ == '__main__':
sol = Solution()
# s = [3, 2, 1]
# print sol.thirdMax(s)
# print sol.thirdMax2(s)
s = [2, 2, 3, 1]
# print sol.thirdMax(s)
print sol.thirdMax2(s)
s = [1, 2]
# print sol.thirdMax(s)
# print sol.thirdMax2(s)
