414. 第三大的数

🟢   🔖  数组 排序  🔗 力扣 LeetCode

题目

Given an integer array nums, return thethird 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 <= 10^4
• -2^31 <= nums[i] <= 2^31 - 1

Follow up: Can you find an O(n) solution?

题目大意

给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数。

示例 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) 的解决方案吗？

解题思路

最直接的思路是对数组进行去重和排序，再根据数组长度返回第三大数或最大值。

但是这种解法的时间复杂度为 O(n logn)，要对数组排序；空间复杂度是 O(n)，要存储去重后的数组。

更优化的思路是，不对整个数组排序，而是维护前三个最大值，遍历一遍数组即可找到第三大数。

• 使用变量 first、second 和 third 来保存前三大的数。
• 遍历数组时，动态更新前三大数。
• 如果 third 存在，就返回第三大数 third；
• 如果 third 不存在，就返回数组中的最大数 first。

复杂度分析

• 时间复杂度：O(n)，线性遍历一次数组。
• 空间复杂度：O(1)，仅使用常数个变量存储前三大数。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var thirdMax = function (nums) {
	let first = -Infinity,
		second = -Infinity,
		third = -Infinity;

	for (let num of nums) {
		if (num === first || num === second || num === third) continue;

		if (num > first) {
			third = second;
			second = first;
			first = num;
		} else if (num > second) {
			third = second;
			second = num;
		} else if (num > third) {
			third = num;
		}
	}

	return third === -Infinity ? first : third;
};

相关题目

题号	标题	题解	标签	难度	力扣
215	数组中的第K个最大元素	[✓]	数组 分治 快速选择 2+	🟠	🀄️ 🔗
2733	既不是最小值也不是最大值		数组 排序	🟢	🀄️ 🔗