20210708力扣第414题：第三大数(java)题目想法评论及答案总结

60 阅读 0 评论 40 点赞

我是靠谱客的博主感性时光，最近开发中收集的这篇文章主要介绍20210708力扣第414题：第三大数(java)题目想法评论及答案总结，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目

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

示例 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) 的解决方案吗？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/third-maximum-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

文章目录

题目
想法
评论及答案
总结

想法

这道题看着不难，就开始了自己的代码，但是写着写着，提交运行发现测试案列好多通不过，才发现自己的问题，其中，主要在出现重复的数字时，只当作一个数字，然后找到第三大数字。

还有一点要注意：如果不存在第三大数字，就返回最大数字。

我开始写的时候没在意重复数字，导致一直出错，所以看了下评论，评论中的方法太好玩了，说循环三次，第一次找第一大，第二次找第二大，第三次找第三大，就能找到，哈哈哈哈。我这样尝试了下，果然可以。

附上代码;

class Solution {
public int thirdMax(int[] nums) {
Arrays.sort(nums);
Integer one = null,two = null,three =null;
if(nums.length< 3)
{
return nums[nums.length-1];
}
else
{
one = nums[nums.length-1];
for(int i =nums.length-1;i>=0;i--)
{
if(nums[i]<one&&one !=null)
{
two = nums[i];
break;
}
}
for(int i =nums.length-1;i>=0;i--)
{
if(two!=null)
{
if(nums[i]<two)
{
three = nums[i];
break;
}
}
}
}
return three==null?one:three;
}
}

说一下我上面代码的问题：
1.需要把这些数字定义成Integer类型，且等于null才可以，最后return可以进行判断。
2.这段代码需要判断two！=null的情况，但是不能写&& ，&&相当于都会执行，two==null时会出现问题。主要是我当时写的是nums[i]<two&&two!=null，将这两个顺序交换一下也就可以了。

 if(two!=null)
{
if(nums[i]<two)
{
three = nums[i];
break;
}
}

3.重点问题，我这个直接使用了Arrays.sort，好像有点投机取巧的意思，这样的话，遍历会很快完成，也达不到O（n）的时间复杂度了。

接下来我来看看评论和答案是怎么写的。

评论及答案

看到评论中极简的方法，用了一个point计数器，太方便了这：

class Solution {
public int thirdMax(int[] nums) {
Arrays.sort(nums);
for (int i = nums.length - 2, point = 2; i > -1; i--) {
if (nums[i] == nums[i + 1]) continue;
if (nums[i] < nums[i + 1]) point--;
if (point == 0) return nums[i];
}
return nums[nums.length - 1];
}
}

好像还有方法，把这个nums转变成set，对set排序，就得到了第三大数字。

class Solution {
public int thirdMax(int[] nums) {
HashSet<Integer> set = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
set.add(nums[i]);
}
if (set.size() < 3) {
return Collections.max(set);
} else {
for (int j = 0; j < 2; j++) {
set.remove(Collections.max(set));
}
return Collections.max(set);
}
}
}
作者：sui-ji-guo-cheng-sui-ji-guo
链接：https://leetcode-cn.com/problems/third-maximum-number/solution/di-san-da-de-shu-java-by-sui-ji-guo-chen-vuhe/