有专业做网站,郑州网站制作专业乐云seo,门户地方网站 策略,html商品页面代码414. 第三大的数
难度#xff1a;简单
题目
给你一个非空数组#xff0c;返回此数组中 第三大的数 。如果不存在#xff0c;则返回数组中最大的数。
示例 1#xff1a;
输入#xff1a;[3, 2, 1]
输出#xff1a;1
解释#xff1a;第三大的数是 1 。示例 2#xf…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) 的解决方案吗
个人题解
思路
用三个变量分别装最大第二大第三大的数一次遍历即可就是要注意条件
class Solution {public int thirdMax(int[] nums) {Integer[] maxArr new Integer[3];for (int num : nums) {if (maxArr[0] null || num maxArr[0]) {maxArr[2] maxArr[1];maxArr[1] maxArr[0];maxArr[0] num;} else if (num ! maxArr[0] (maxArr[1] null || num maxArr[1])) {maxArr[2] maxArr[1];maxArr[1] num;} else if (num ! maxArr[0] num ! maxArr[1] (maxArr[2] null || num maxArr[2])) {maxArr[2] num;}}return maxArr[1] null || maxArr[2] null ? maxArr[0] : maxArr[2];}
}复杂度分析
时间复杂度O(n)空间复杂度O(1)
官方题解
方法一排序
将数组从大到小排序后从头开始遍历数组通过判断相邻元素是否不同来统计不同元素的个数。如果能找到三个不同的元素就返回第三大的元素否则返回最大的元素。
class Solution {public int thirdMax(int[] nums) {Arrays.sort(nums);reverse(nums);for (int i 1, diff 1; i nums.length; i) {if (nums[i] ! nums[i - 1] diff 3) { // 此时 nums[i] 就是第三大的数return nums[i];}}return nums[0];}public void reverse(int[] nums) {int left 0, right nums.length - 1;while (left right) {int temp nums[left];nums[left] nums[right];nums[right] temp;left;right--;}}
}复杂度分析
时间复杂度O(n logn)空间复杂度O(logn)
方法二有序集合
我们可以遍历数组同时用一个有序集合来维护数组中前三大的数。具体做法是每遍历一个数就将其插入有序集合若有序集合的大小超过 3就删除集合中的最小元素。这样可以保证有序集合的大小至多为 3且遍历结束后若有序集合的大小为 3其最小值就是数组中第三大的数若有序集合的大小不足 3那么就返回有序集合中的最大值。
class Solution {public int thirdMax(int[] nums) {TreeSetInteger s new TreeSetInteger();for (int num : nums) {s.add(num);if (s.size() 3) {s.remove(s.first());}}return s.size() 3 ? s.first() : s.last();}
}复杂度分析
时间复杂度O(n)空间复杂度O(1)
方法三一次遍历
class Solution {public int thirdMax(int[] nums) {long a Long.MIN_VALUE, b Long.MIN_VALUE, c Long.MIN_VALUE;for (long num : nums) {if (num a) {c b;b a;a num;} else if (a num num b) {c b;b num;} else if (b num num c) {c num;}}return c Long.MIN_VALUE ? (int) a : (int) c;}
}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;}
}复杂度分析
时间复杂度O(n)空间复杂度O(1)
作者力扣官方题解 链接https://leetcode.cn/problems/third-maximum-number/solutions/1032401/di-san-da-de-shu-by-leetcode-solution-h3sp/ 来源力扣LeetCode 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。
