leetcode with python:414. Third Maximum Number

题目:

Given an integer array nums, return the third distinct maximum number in this array. If the third maximum does not exist, return the maximum number.

给定一阵列,找出第三大的数,若不存在,则回传最大的数

我一开始採用比较简单的方法

class Solution:    def thirdMax(self, nums: List[int]) -> int:        s=sorted(set(nums))                if len(s)>=3:            return s[-3]        else:            return s[-1]

将该阵列转为set后排序
若其长度大于等于3,回传倒数第三项
反之,回传最后一项
最后执行时间57ms(faster than 91.03%)

但题目后面又说了一句:

Can you find an O(n) solution?

上面的解法因为用到了sort
所以时间複杂度为O(nlogn),不符合要求

现在我们要用O(n)解

class Solution:    def thirdMax(self, nums: List[int]) -> int:        n1=None        n2=None        n3=None                for i in nums:            if n1==None or i>n1:                n1,n2,n3=i,n1,n2            elif (n2==None or i>n2) and i!=n1:                n2,n3=i,n2            elif (n3==None or i>n3) and i!=n1 and i!=n2:                n3=i                                        if n3==None:            return n1        else:            return n3

预设三个变数(n1,n2,n3)为None
开始遍历这个阵列
若n1为None或者遍历的该数大于n1
那n1设为该数
若n2为None或者遍历的该数大于n2,且该数不等于n1
那n2设为该数
若n3为None或者遍历的该数大于n3,且该数不等于n1,n2
那n3设为该数
前一个条件失败才会去思考下一个条件,所以用elif

若最后n3为None(代表第三大的数不存在),回传n1
反之直接回传n3
最后执行时间54ms(faster than 94.99%)

那我们下题见