leetcode414-- Third Maximum Number

leetcode414-- 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.


这个的第三大指的就是不记重数的第三大。要求用O(n)

其实这个的做法就像求最大值的原理是一样的,只不过这时候是求第三大,先回想一下求第二大是如何的过程,

假设max1, max2, max3分别代表之前的见到的数字中的第一大,第二大,和第二大,它们都初始化为很小的数字,

然后假设现在对于x in nums而言, 如果x>max1 说明max1要更新了,而且之前的max1这时候最多就是第二大了,所以第二大要更新成max1, 同理第三大要更新成max2,

如果x<max1, x>max2 (等于的全部都直接pass掉), 这意味着之前的max1还有可能是最大值,但是现在的max2不可能是第二大了,要把它更新,同理也要更新第三大。

最终如下

class Solution(object):
    def thirdMax(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ### method1
        #nums = list(set(nums))
        #nums.sort()
        
        #try:
        #    return nums[len(nums)-3]
        #except:
        #    return nums[-1]
        
        ### method2.
        
        max1, max2, max3 = -float("inf"), -float("inf"), -float("inf")
        
        for x in nums:
            if x==max1 or x==max2 or x==max3:
                continue
            
            if x>max1:
                max1, max2, max3 = x, max1, max2
            elif x>max2:
                max2, max3 = x, max2
            elif x>max3:
                max3 = x
                
        
        if max3 != -float("inf"):
            return max3
        else:
            return max1
        
        
        

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦