Third Maximum Number

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.

题目大意：

给定一个整数数组，返回数组中第3大的数，如果不存在，则返回最大的数字。时间复杂度应该是O(n)或者更少。

解题思路：

利用变量first, second, third分别记录数组第1,2,3大的数字, 然后我们遍历数组，如果遍历到的数字大于当前第一大的数first，那么三个变量各自错位赋值，如果当前数字大于second，小于first，那么就更新second和third，如果当前数字大于third，小于second，那就只更新third，

遍历一次数组即可，时间复杂度O(n)

class Solution(object):
    def thirdMax(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        p1 = p2 = p3 = None
        for num in nums:
            if num > p1:
                p1,p2,p3=num,p1,p2
            elif p1 > num > p2:
                p2,p3 = num,p2
            elif p2>num>p3:
                p3 = num

        return p3 if p3 != None else p1

def thirdMax(self, nums):
        nums = set(nums)
        if len(nums) < 3:
            return max(nums)
        nums.remove(max(nums))
        nums.remove(max(nums))
        return max(nums)