題目:

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%)

那我們下題見