第三大的数

Leetcode Link: 414. 第三大的数 - 力扣（LeetCode）

题目

解法一

思路：

1. 去重
2. 判断长度
3. 排序
4. 取第三个大的数字

题解：

class Solution:
    def thirdMax(self, nums: List[int]) -> int:
        nums = list(set(nums))
        if len(nums) < 3:
            return max(nums)
        nums.sort(reverse=True)
        return nums[2]

解法二

思路：复杂度 $O(N)$ 的解法

1. 提前新建存储前3个大的数字的变量
2. 遍历并检查每次的数字与当前 3 个数字的关系

细节

• 如果遍历的 num 已经是前 3 大的数字了，必需跳过（等价于去重）
• 如果有新加入的数字，必需用insert(idx, val)

题解：

class Solution:
    def thirdMax(self, nums: List[int]) -> int:
        self.bucket = [-float('inf')] * 3
        for val in nums:
            self.check_and_replace(val)
        return self.bucket[2] if self.bucket[2] != -float('inf') else self.bucket[0]
    
    def check_and_replace(self, num):
        if num in self.bucket:
            return 
        if num > self.bucket[0]:
            self.bucket.pop()
            self.bucket.insert(0, num)
        elif self.bucket[0] > num > self.bucket[1]:
            self.bucket.pop()
            self.bucket.insert(1, num)
        elif self.bucket[1] > num > self.bucket[2]:
            self.bucket[2] = num
 

解法三

思路：

题解：

启发和联系