📢前言
🌲 每天打卡一道算法题,既是一个学习过程,又是一个分享的过程😜 🌲 提示:本专栏解题 编程语言一律使用 C# 和 Java 两种进行解题 🌲 要保持一个每天都在学习的状态,让我们一起努力成为算法大神吧🧐! 🌲 今天是力扣算法题持续打卡第54天🎈!
🌲原题样例:. 第三大的数
给你一个非空数组,返回此数组中 第三大的数
。如果不存在,则返回数组中最大的数。
示例:
输入:[ 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
两种编程语言进行解题 一些方法也是参考力扣大神写的,也是边学习边分享,再次感谢算法大佬们 那今天的算法题分享到此结束啦,明天再见!