第三大的数
难度:
标签:
题目描述
给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数。
示例 1：
输入：[3, 2, 1] 输出：1 解释：第三大的数是 1 。
示例 2：
输入：[1, 2] 输出：2 解释：第三大的数不存在, 所以返回最大的数 2 。
示例 3：
输入：[2, 2, 3, 1] 输出：1 解释：注意，要求返回第三大的数，是指在所有不同数字中排第三大的数。 此例中存在两个值为 2 的数，它们都排第二。在所有不同数字中排第三大的数为 1 。
提示：
1 <= nums.length <= 104-231 <= nums[i] <= 231 - 1
进阶：你能设计一个时间复杂度 O(n) 的解决方案吗？
代码结果
运行时间: 18 ms, 内存: 17.4 MB
/*
* 思路：
* 1. 将数组转化为一个集合，以移除重复元素。
* 2. 将集合转换为流，并排序。
* 3. 如果集合的大小小于3，返回集合中的最大值。
* 4. 如果集合的大小大于等于3，返回排序后的集合中倒数第三个值。
*/
import java.util.*;
import java.util.stream.Collectors;
public class Solution {
public int thirdMax(int[] nums) {
List<Integer> distinctNums = Arrays.stream(nums)
.boxed()
.collect(Collectors.toSet())
.stream()
.sorted(Collections.reverseOrder())
.collect(Collectors.toList());
if (distinctNums.size() < 3) {
return distinctNums.get(0);
}
return distinctNums.get(2);
}
}解释
方法:
该题解的思路是先将原数组去重，然后判断去重后的数组长度：如果长度大于等于3，则返回排序后的数组的倒数第三个元素，即第三大的数；否则返回去重后数组的最大值。
时间复杂度:
O(nlogn)
空间复杂度:
O(n)
代码细节讲解
🦆
在解决方案中，使用了集合来去重，这种方法是否能保证所有的元素都被正确处理，特别是在存在负数或极大值的情况下？
▷🦆
解题思路中提到，如果去重后的数组长度大于等于3，则进行排序并返回倒数第三个元素。请问在什么情况下会存在去重后数组长度小于3的情况？
▷