地址
难度
简单
题目
给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数。
示例 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) 的解决方案吗？
思路
- 排序
题目是求第三大的数字，并且数组中有重复的数字。
先想到的就是利用 Set 去重，然后进行排序，取第三大的数字。
时间复杂度：O(nlogn)，空间复杂度为 O(n)
class Solution {
public int thirdMax(int[] nums) {
// 去重
Set<Integer> set = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
set.add(nums[i]);
}
ArrayList<Integer> arrayList = new ArrayList<>(set);
// 排序
Collections.sort(arrayList);
return arrayList.size() < 3 ? arrayList.get(arrayList.size() - 1) : arrayList.get(arrayList.size() - 3);
}
}
- 有序集合
利用 TreeSet 的特性。遍历数组，用一个TreeSet来维护数组中前三大的数。
具体做法是每遍历一个数，就将其插入有序集合，若有序集合的大小超过 3，就删除集合中的最小元素。这样可以保证有序集合的大小至多为 3，且遍历结束后，若有序集合的大小为 3，其最小值就是数组中第三大的数；若有序集合的大小不足 3，那么就返回有序集合中的最大值。
时间复杂度：O(n)，空间复杂度为 O(n)。
TreeSet 的特性：
* TreeSet中存储的类型必须是一致的，不能一下存int，一下又存string
* TreeSet在遍历集合元素时，是有顺序的【从小到大】
* 排序：当向TreeSet中添加自定义对象时，有2种排序方法，1：自然排序 2、定制排序
* 没有带索引的方法，所以不能使用普通的for循环遍历
* 由于是set集合，所以不包含重复的集合
class Solution {
public int thirdMax(int[] nums) {
TreeSet<Integer> treeSet =new TreeSet<>();
for(int x:nums){
treeSet.add(x);
if(treeSet.size()>3){
treeSet.remove(treeSet.first());
}
}
return treeSet.size()==3?treeSet.first():treeSet.last();
}
}
- 一次遍历
利用三个变量 a、b 和 c 来维护数组中的最大值、次大值和第三大值，以模拟方法二中的插入和删除操作。为方便编程实现，我们将其均初始化为 null。
遍历数组，对于数组中的元素 num：
若 num>a，我们将 c 替换为 b，b 替换为 a，a 替换为 num，这模拟了将 num插入有序集合，并删除有序集合中的最小值的过程
若 a>num>b，类似地，将 c 替换为 b，b 替换为 num，a 保持不变
若 b>num>c，类似地，将 c 替换为 num，a 和 b 保持不变
其余情况不做处理。
遍历结束后，若 ccc 仍然为 null，则说明数组中不存在三个或三个以上的不同元素，即第三大的数不存在，返回 a，否则返回 c。
class Solution {
public int thirdMax(int[] nums) {
Integer a = null, b = null, c = null;
for (int x : nums) {
if (a == null || x > a) {
c = b;
b = a;
a = x;
} else if (a > x && (b == null || x > b)) {
c = b;
b = x;
} else if (b != null && b > x && (c == null || x > c)) {
c = x;
}
}
return c == null ? a : c;
}
}