给你一个非空数组,返回此数组中 第三大的数
。如果不存在,则返回数组中最大的数。
示例:
输入:[3, 2, 1]
输出:1
解释:第三大的数是 1 。
示例 2:
输入:[1, 2]
输出:2
解释:第三大的数不存在, 所以返回最大的数 2 。
示例3
输入:[2, 2, 3, 1]
输出:1
解释:注意,要求返回第三大的数,是指在所有不同数字中排第三大的数。
此例中存在两个值为 2 的数,它们都排第二。在所有不同数字中排第三大的数为 1 。
说明:
提示:
代码:
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%的用户
代码
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 )
思路解析
代码:
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 )
代码
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
两种编程语言进行解题