414. 第三大的数
题目描述
输入一个非空整数数组 nums。先去掉重复值，只看不同的数值，再从大到小排序。
如果不同的数值至少有三个，返回排第三的那个。否则返回其中最大的数。
示例 1
输入：nums = [3,2,1] 输出：1
解释：不同的数为 3、2、1，第三大是 1。
示例 2
输入：nums = [1,2] 输出：2
解释：只有两个不同的数，返回最大的 2。
示例 3
输入：nums = [2,2,3,1] 输出：1
解释：两个 2 只算一个值，不同的数为 3、2、1，第三大是 1。
数据范围
1 <= nums.length <= 10^4-2^31 <= nums[i] <= 2^31 - 1
进阶：能否在 O(n) 时间内完成？
解题思路：一次遍历维护前三大
一次遍历，维护三个槽位 a > b > c，分别是目前见过的第一、第二、第三大的不同数，空槽用 None 表示。对每个 x：如果它已经在槽位里，跳过；否则找到它应在的位置，把它后面的槽位依次往下挤一格，最小的被挤出去。结束时 c 非空就返回 c，否则返回 a。
为什么正确
处理完前 i 个数后，a、b、c 是 nums[0..i-1] 中最大的至多三个不同的数，且严格递减。
复杂度分析
时间 O(n)，空间 O(1)。
易错点
重复的数只算一次，必须先判重再比较；不要用 -2^31 当“空”的哨兵，因为它本身可能就是第三大的数（如 [1,2,-2147483648]），C++/Java 里可用 long 的最小值。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def thirdMax(self, nums: List[int]) -> int:
a = b = c = None
for x in nums:
if x == a or x == b or x == c:
continue
if a is None or x > a:
a, b, c = x, a, b
elif b is None or x > b:
b, c = x, b
elif c is None or x > c:
c = x
return a if c is None else cclass Solution {
public int thirdMax(int[] nums) {
long a = Long.MIN_VALUE, b = Long.MIN_VALUE, c = Long.MIN_VALUE;
for (int x : nums) {
if (x == a || x == b || x == c) {
continue;
}
if (x > a) {
c = b; b = a; a = x;
} else if (x > b) {
c = b; b = x;
} else if (x > c) {
c = x;
}
}
return (int) (c == Long.MIN_VALUE ? a : c);
}
}class Solution {
public:
int thirdMax(vector<int>& nums) {
long long a = LLONG_MIN, b = LLONG_MIN, c = LLONG_MIN;
for (int x : nums) {
if (x == a || x == b || x == c) {
continue;
}
if (x > a) {
c = b; b = a; a = x;
} else if (x > b) {
c = b; b = x;
} else if (x > c) {
c = x;
}
}
return c == LLONG_MIN ? a : c;
}
};func thirdMax(nums []int) int {
a, b, c := math.MinInt64, math.MinInt64, math.MinInt64
for _, x := range nums {
if x == a || x == b || x == c {
continue
}
if x > a {
a, b, c = x, a, b
} else if x > b {
b, c = x, b
} else if x > c {
c = x
}
}
if c == math.MinInt64 {
return a
}
return c
}var thirdMax = function(nums) {
let a = -Infinity, b = -Infinity, c = -Infinity;
for (const x of nums) {
if (x === a || x === b || x === c) {
continue;
}
if (x > a) {
[a, b, c] = [x, a, b];
} else if (x > b) {
[b, c] = [x, b];
} else if (x > c) {
c = x;
}
}
return c === -Infinity ? a : c;
};function thirdMax(nums: number[]): number {
let a = -Infinity, b = -Infinity, c = -Infinity;
for (const x of nums) {
if (x === a || x === b || x === c) {
continue;
}
if (x > a) {
[a, b, c] = [x, a, b];
} else if (x > b) {
[b, c] = [x, b];
} else if (x > c) {
c = x;
}
}
return c === -Infinity ? a : c;
}其他解法
排序后按顺序数出第三个不同的数，简单但要 O(n log n)；一次遍历只维护三个变量，时间 O(n)、空间 O(1)。
解法 2：排序 时间 O(n log n)，空间 O(log n)
把数组降序排序。从前往后遍历，遇到和前一个元素不同的数时，不同数字计数加 1。计数到 3 时返回当前数。遍历结束仍不足 3 个不同数字时，返回最大值 nums[0]。
思路最直接，代码短。排序带来 O(n log n) 时间，并且会修改原数组。
class Solution:
def thirdMax(self, nums):
nums.sort(reverse=True)
diff = 1
for i in range(1, len(nums)):
if nums[i] != nums[i - 1]:
diff += 1
if diff == 3:
return nums[i]
return nums[0]class Solution {
public int thirdMax(int[] nums) {
Arrays.sort(nums);
int n = nums.length;
int diff = 1;
for (int i = n - 2; i >= 0; i--) {
if (nums[i] != nums[i + 1]) {
diff++;
if (diff == 3) return nums[i];
}
}
return nums[n - 1];
}
}class Solution {
public:
int thirdMax(vector<int>& nums) {
sort(nums.begin(), nums.end(), greater<int>());
int diff = 1;
for (int i = 1; i < (int)nums.size(); i++) {
if (nums[i] != nums[i - 1]) {
diff++;
if (diff == 3) return nums[i];
}
}
return nums[0];
}
};func thirdMax(nums []int) int {
sort.Sort(sort.Reverse(sort.IntSlice(nums)))
diff := 1
for i := 1; i < len(nums); i++ {
if nums[i] != nums[i-1] {
diff++
if diff == 3 {
return nums[i]
}
}
}
return nums[0]
}var thirdMax = function(nums) {
nums.sort((a, b) => b - a);
let diff = 1;
for (let i = 1; i < nums.length; i++) {
if (nums[i] !== nums[i - 1]) {
diff++;
if (diff === 3) return nums[i];
}
}
return nums[0];
};function thirdMax(nums: number[]): number {
nums.sort((a, b) => b - a);
let diff = 1;
for (let i = 1; i < nums.length; i++) {
if (nums[i] !== nums[i - 1]) {
diff++;
if (diff === 3) return nums[i];
}
}
return nums[0];
}