【算法千题案例】⚡️每日LeetCode打卡⚡️——54.第三大的数
【算法千题案例】⚡️每日LeetCode打卡⚡️——54.第三大的数
呆呆敲代码的小Y
发布于 2021-10-15 15:09:09
发布于 2021-10-15 15:09:09
请添加图片描述
原题样例：. 第三大的数
给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数。
示例:
输入：[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
C#方法：排序
- 将数组从大到小排序后，从头开始遍历数组，通过判断相邻元素是否不同，来统计不同元素的个数。
- 如果能找到三个不同的元素，就返回第三大的元素，否则返回最大的元素。
代码：
public class Solution {
public int ThirdMax(int[] nums) {
Array.Sort(nums);
Array.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];
}
}执行结果
通过
执行用时：92 ms，在所有 C# 提交中击败了58.36%用户
内存消耗：37.4 MB，在所有 C# 提交中击败了8.56%的用户C#方法二：有序集合
- 我们可以遍历数组，同时用一个有序集合来维护数组中前三大的数。
- 具体做法是每遍历一个数，就将其插入有序集合，若有序集合的大小超过 333，就删除集合中的最小元素。
- 这样可以保证有序集合的大小至多为 333，且遍历结束后，若有序集合的大小为 333，其最小值就是数组中第三大的数； 若有序集合的大小不足 333，那么就返回有序集合中的最大值。
代码
public class Solution {
public int ThirdMax(int[] nums) {
SortedSet<int> s = new SortedSet<int>();
foreach (int num in nums) {
s.Add(num);
if (s.Count > 3) {
s.Remove(s.Min);
}
}
return s.Count == 3 ? s.Min : s.Max;
}
}执行结果
通过
执行用时：92 ms，在所有 C# 提交中击败了58.36%的用户
内存消耗：38.4 MB，在所有 C# 提交中击败了5.21%的用户复杂度分析
时间复杂度：O( n )
空间复杂度：O( 1 )Java 方法一：排序
思路解析
- 将数组从大到小排序后，从头开始遍历数组，通过判断相邻元素是否不同，来统计不同元素的个数。
- 如果能找到三个不同的元素，就返回第三大的元素，否则返回最大的元素。
代码：
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--;
}
}
}执行结果
通过
执行用时：2 ms，在所有 Java 提交中击败了57.82%的用户
内存消耗：38.5 MB，在所有 Java 提交中击败了16.17%的用户复杂度分析
时间复杂度：O( nlogn )
空间复杂度：O( logn ) Java方法二：有序集合
- 我们可以遍历数组，同时用一个有序集合来维护数组中前三大的数。
- 具体做法是每遍历一个数，就将其插入有序集合，若有序集合的大小超过 333，就删除集合中的最小元素。
- 这样可以保证有序集合的大小至多为 333，且遍历结束后，若有序集合的大小为 333，其最小值就是数组中第三大的数； 若有序集合的大小不足 333，那么就返回有序集合中的最大值。
代码
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();
}
}执行结果
通过
执行用时：4 ms，在所有 Java 提交中击败了39.49%的用户
内存消耗：38.3 MB，在所有 Java 提交中击败了59.56%的用户复杂度分析
时间复杂度：O( n )
空间复杂度：O( 1 )总结
- 今天是力扣算法题打卡的第五十四天！
- 文章采用
C#和Java两种编程语言进行解题 - 一些方法也是参考力扣大神写的，也是边学习边分享，再次感谢算法大佬们
- 那今天的算法题分享到此结束啦，明天再见！
请添加图片描述
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2021-10-14 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录