414.-第三大的数
目录
414. 第三大的数
题目描述
给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数。
示例 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) 的解决方案吗？
尝试做法
本来还想用sort一键搞定，为了进阶条件，还是研究一下这题吧
class Solution {
public int thirdMax(int[] nums) {
long ans = 0;
int len = nums.length;
if(len == 1) return nums[0];
if(len == 2) return Math.max(nums[0],nums[1]);
Long first = Long.MIN_VALUE, second = Long.MIN_VALUE,third = Long.MIN_VALUE;
for(long i : nums){
if(i > first){
third = second;
second = first;
first = i;
}else if(i > second && i < first){
third = second;
second = i;
}else if(i > third && i < second){
third = i;
}
}
if(third == Long.MIN_VALUE){
ans = first;
}else{
ans = third;
}
return (int)ans;
}
}被各种输入卡住，然后一步步完善
被输入中含有int最小值的情况卡了很久，后面换成long来赋初始值
有时候正常的输入会产生错误输出，发现是一开始写的判断条件（i > second && i ！= first）
要改成（i > second && i < first）才行
推荐做法
class Solution {
public int thirdMax(int[] nums) {
Integer a = null, b = null, c = null;
for (int num : nums) {
if (a == null || num > a) {
c = b;
b = a;
a = num;
} else if (a > num && (b == null || num > b)) {
c = b;
b = num;
} else if (b != null && b > num && (c == null || num > c)) {
c = num;
}
}
return c == null ? a : c;
}
}
作者：力扣官方题解
链接：https://leetcode.cn/problems/third-maximum-number/solutions/1032401/di-san-da-de-shu-by-leetcode-solution-h3sp/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。值得一提的是官方题解给了我另一种赋初始值的思路，就是用包装类直接赋值空指针。
class Solution {
public int thirdMax(int[] nums) {
TreeSet<Integer> s = new TreeSet<Integer>();
for (int num : nums) {
s.add(num);
if (s.size() > 3) {
s.remove(s.first());
}
}
return s.size() == 3 ? s.first() : s.last();
}
}
作者：力扣官方题解
链接：https://leetcode.cn/problems/third-maximum-number/solutions/1032401/di-san-da-de-shu-by-leetcode-solution-h3sp/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。还有一种做法是使用有序集合TreeSet