当前位置：首页 > article >正文

LeetCode题练习与总结：第三大的数--414

article 2024/11/28 5:02:28

一、题目描述

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

示例 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

二、解题思路

首先我们可以使用三个变量来分别存储当前找到的第一大、第二大和第三大的数，分别记为 firstMax, secondMax, thirdMax。
遍历数组 nums，对于每个元素 num，我们需要做以下判断：
- 如果 num 大于 firstMax，则更新 thirdMax 为 secondMax，secondMax 为 firstMax，firstMax 为 num。
- 如果 num 介于 firstMax 和 secondMax 之间（不包括等于 firstMax），则更新 thirdMax 为 secondMax，secondMax 为 num。
- 如果 num 介于 secondMax 和 thirdMax 之间（不包括等于 secondMax），则更新 thirdMax 为 num。
在更新过程中，我们需要保证 firstMax, secondMax, thirdMax 是不同的数。
遍历结束后，如果 thirdMax 仍然是初始值（例如可以设为 Integer.MIN_VALUE），说明没有第三大的数，此时返回 firstMax；否则返回 thirdMax。

三、具体代码

class Solution {
    public int thirdMax(int[] nums) {
        long firstMax = Long.MIN_VALUE, secondMax = Long.MIN_VALUE, thirdMax = Long.MIN_VALUE;
        
        for (int num : nums) {
            if (num > firstMax) {
                thirdMax = secondMax;
                secondMax = firstMax;
                firstMax = num;
            } else if (num > secondMax && num < firstMax) {
                thirdMax = secondMax;
                secondMax = num;
            } else if (num > thirdMax && num < secondMax) {
                thirdMax = num;
            }
        }
        
        // 如果thirdMax没有更新过，说明没有第三大的数，返回firstMax
        if (thirdMax == Long.MIN_VALUE) {
            return (int)firstMax;
        }
        
        return (int)thirdMax;
    }
}

注意：这里使用 long 类型而不是 int 来存储最大值是为了防止整数溢出。例如，当数组中的最大值接近 Integer.MAX_VALUE 时，如果再遇到一个比它大的数，将会发生溢出。使用 long 可以避免这种情况。在最后返回结果时，我们确保结果不会超过 int 的范围。

四、时间复杂度和空间复杂度

1. 时间复杂度

代码中有一个 for 循环，该循环遍历数组 nums 中的每个元素。
在循环内部，每次迭代中，我们只进行常数时间的操作（比较和赋值）。
因此，循环的时间复杂度是 O(n)，其中 n 是数组 nums 的长度。

综上所述，整个 thirdMax 方法的时间复杂度是 O(n)。

2. 空间复杂度

在方法中，我们使用了三个变量 firstMax, secondMax, thirdMax 来存储第一、第二和第三大的数。
这些变量都是固定大小的，不随输入数组 nums 的大小而变化。
因此，除了输入数组本身占用的空间外，额外的空间占用是常数级别的。

综上所述，整个 thirdMax 方法的空间复杂度是 O(1)。

五、总结知识点

数组遍历：
- 使用增强型 for 循环（for-each loop）来遍历数组中的每个元素。
基本数据类型：
- 使用 int 类型来处理数组中的元素。
- 使用 long 类型来存储最大值，以避免整数溢出问题。
常量：
- 使用 Long.MIN_VALUE 来初始化最大值变量，确保它们在第一次比较之前都是最小值。
条件判断：
- 使用 if-else if 语句来根据当前元素与已存储的最大值之间的关系来更新最大值变量。
逻辑比较：
- 使用比较运算符（> 和 <）来比较数字大小。
变量赋值：
- 使用赋值操作来更新最大值变量。
类型转换：
- 在返回结果之前，使用类型转换 (int) 将 long 类型的变量转换为 int 类型。
边界条件处理：
- 检查 thirdMax 是否仍然为 Long.MIN_VALUE 来判断是否找到了第三大的数，如果没有找到，则返回 firstMax。
返回值：
- 使用 return 语句来返回最终的计算结果。