7/7 每日一題(返回數組第三大的數字,如果沒有則返回最大值)

 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.

 

Example 1:

Input: nums = [3,2,1]
Output: 1
Explanation:
The first distinct maximum is 3.
The second distinct maximum is 2.
The third distinct maximum is 1.

Example 2:

Input: nums = [1,2]
Output: 2
Explanation:
The first distinct maximum is 2.
The second distinct maximum is 1.
The third distinct maximum does not exist, so the maximum (2) is returned instead.

Example 3:

Input: nums = [2,2,3,1]
Output: 1
Explanation:
The first distinct maximum is 3.
The second distinct maximum is 2 (both 2's are counted together since they have the same value).
The third distinct maximum is 1.

 

Constraints:

• 1 <= nums.length <= 104
• -231 <= nums[i] <= 231 - 1

class Solution:

    def thirdMax(self, nums: List[int]) -> int:

        nums_set=set(nums)#除掉重複的值

        i=0 #計算第幾個

        first_third=[]

           

        while i<3: #只記錄前3大資料

            if nums_set:

                max_element=max(nums_set)

                nums_set.discard(max_element)

                #移除最大項

    (discard()可以避免移除不存在項目發生的例外,但這裡已經用if避免,因為max()不能是空集合)

                first_third.append(max_element)

            i+=1

        if len(first_third)<3:

            return first_third[0]

        return first_third[-1]

           

-----------------------------參考解答

class Solution: def thirdMax(self, nums: List[int]) -> int: nums=list(set(nums)) #去掉重複的值再轉回列表 if len(nums)<3: #如果不滿足3項直接返回最大值 return max(nums) n=[-i for i in nums]

#將不重複元素取相反數放入堆中(使用heapq.heapify()) ,配合最小堆特性最大變最小

#ex: nums=[1,2,3] >>n=[-1,-2,-3] heapq.heapify(n) #這個函式將列表n轉換最小堆(最小的元素變成根結點)

        排序最小的在前面所以會再變成[-3,-2,-1] for i in range(3): #遍歷堆,逐次彈出元素直到彈出第三大元素 poping=heapq.heappop(n) #他會一次彈出-3,-2,-1 if i==2: return -(poping) #回傳第3大