华为 OD 训练营 · 题解精讲
LeetCode414、第三大的数
LeetCode414、第三大的数 视频地址：
题目描述
给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数。
示例 1： 输入：[3, 2, 1] 输出：1 解释：第三大的数是 1 。 示例 2： 输入：[1, 2] 输出：2 解释：第三大的数不存在, 所以返回最大的数 2 。 示例 3： 输入：[2, 2, 3, 1] 输出：1 解释：注意，要求返回第三大的数，是指在所有不同数字中排第三大的数。 此例中存在两个值为 2 的数，它们都排第二。在所有不同数字中排第三大的数为 1 。
提示： 1 <= nums.length <= 10(4) -2(31) <= nums[i] <= 2(31)1
进阶：你能设计一个时间复杂度 O(n) 的解决方案吗？
题目解析
解题思路
题目要求返回数组中第三大的不同数字，若不存在则返回最大值。参考代码采用去重 + 三变量扫描的方法。
首先利用 set 去除重复元素，得到所有不同数字的列表。若去重后元素个数小于 3，直接返回原数组最大值。否则，先取前三个数排序初始化 first、second、third（分别表示第一大、第二大、第三大），然后遍历剩余元素，根据当前数字与三个变量的比较结果，依次更新这三个变量。最终返回 third。
关键步骤
1. 去重：set(nums) 去除重复，保证只考虑不同数字。 2. 初始化三变量：取去重列表前三个数，降序排序后赋值给 first、second、third。 3. 遍历更新：对剩余每个数字 num：
- 若
num > first：将third、second、first依次后移，first更新为num。 - 若
second < num < first：将third更新为second，second更新为num。 - 若
third < num < second：将third更新为num。
更新过程示意图（以 num > first 为例）：
初始: first=5, second=3, third=1
num=7: third=3, second=5, first=7复杂度分析
- 时间复杂度：O(n)。去重操作 O(n)，排序前三个数 O(1)，遍历剩余元素 O(n)。
- 空间复杂度：O(n)。
set存储所有不同元素，最坏情况下与原数组等长。
参考代码
class Solution:
def thirdMax(self, nums: List[int]) -> int:
nums_no_repeat = list(set(nums))# 使用set()去除重复元素
if len(nums_no_repeat) < 3: # 若去重后的列表长度小于3，返回最大元素
return max(nums)
# 找到去重列表前三个数中的第一、第二、第三大的数
first, second, third = sorted(nums_no_repeat[0:3], reverse = 1)
for num in nums_no_repeat[3:]: # 从第四位开始，遍历去重列表
if num > first: # 若num大于第一大的数，则：
third = second # 修改第三大的数为原来第二大的数
second = first # 修改第二大的数为原来第一大的数
first = num # 修改第一大的数为num
elif second < num < first: # 若num位于第一大的数和第二大的数之间，则：
third = second # 修改第三大的数为原来第二大的数
second = num # 修改第二大的数为num
elif third < num < second: # 若num位于第二大的数和第三大的数之间，则：
third = num # 修改第三大的数为num
return third # 遍历结束，返回第三大的数
四、复杂度分析
时间复杂度：O(n)。
空间复杂度：O(n)。