抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

题目描述

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

实例

输入:[3, 2, 1]
输出:1
解释:第三大的数是 1 。

输入:[1, 2]
输出:2
解释:第三大的数不存在, 所以返回最大的数 2 。

输入:[2, 2, 3, 1]
输出:1
解释:注意,要求返回第三大的数,是指在所有不同数字中排第三大的数。
此例中存在两个值为 2 的数,它们都排第二。在所有不同数字中排第三大的数为 1 。

解题方法

我们只需要对数组进行一次扫描就可以计算出结果。

复杂度分析

时间复杂度:O(N)O(N)

空间复杂度:O(1)O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public int thirdMax(int[] nums) {
//三个数存放
//第一个是三个数中最大的
long one = Long.MIN_VALUE;
long two = Long.MIN_VALUE;
//三个数中最小的
long three = Long.MIN_VALUE;

//遍历数组
for(int num : nums) {
if(num == one || num == two || num < three) {
continue;
}
//插入位置确定
//注意数组重复问题
if(num > one) {
three = two;
two = one;
one = num;
} else if(num > two && num < one) {
three = two;
two = num;
} else if(num < two) {
three = num;
}
}
//判断three是不是变过
if(three == Long.MIN_VALUE) {
return (int)one;
}
return (int)three;
}
}

用户交流区

温馨提示: 遵纪守法, 友善评论!





津ICP备19009605号

WordCount24k