leetcode414-第三大的数
程序员文章站
2022-04-25 17:41:27
...
题目描述
给定一个非空数组,返回此数组中第三大的数。如果不存在,则返回数组中最大的数。要求算法时间复杂度必须是O(n)。
示例
输入: [3, 2, 1]
输出: 1
解释: 第三大的数是 1.
输入: [1, 2]
输出: 2
解释: 第三大的数不存在, 所以返回最大的数 2 .
输入: [2, 2, 3, 1]
输出: 1
解释: 注意,要求返回第三大的数,是指第三大且唯一出现的数。
存在两个值为2的数,它们都排第二。
解题思路
1.用三个变量记录最大的三个数,遍历的同时更新
先对数组进行排序,再一次遍历,但此时不满足时间复杂度为 O(n)的要求
java代码如下
import java.util.Arrays;
class Solution {
public int thirdMax(int[] nums) {
if(nums.length == 1){ //只有一个元素
return nums[0];
}
if(nums.length == 2){ //只有两个元素
return Math.max(nums[0],nums[1]);
}
///////////////大于或者等于三个元素
Arrays.sort(nums); //先排序,方便对重复元素的处理
int first = nums[0];
int second = Integer.MIN_VALUE;
int third = Integer.MIN_VALUE;
int count = 1; //count标志不同值的元素的个数
for (int i = 1; i < nums.length; i++) {
if(nums[i] == nums[i - 1]){
continue;
} //该元素为已重复元素则直接跳过
count++; //和之前元素不一样则不同元素个数加1
if(nums[i] > first){
third = second;
second = first;
first = nums[i];
}else if((nums[i] > second) && (nums[i] < first)){
third = second;
second = nums[i];
}else if((nums[i] > third) && (nums[i] < second)){
third = nums[i];
}else {
continue;
}
}
if(count < 3){ //如果不同元素个数小于3,则不存在第三大的数
return first;
}
return third;
}
}
运行结果如下
2.优化
我们并不需要先对数组进行排序,在if-else逻辑判断中没有加等号已经默认消除了重复元素带来的影响
java代码如下
class Solution {
public int thirdMax(int[] nums) {
//并不需要再对一个元素或者两个元素单独判断
int first = Integer.MIN_VALUE;
int second = Integer.MIN_VALUE;
int third = Integer.MIN_VALUE;
int count = 0;
boolean flag = true;
for (int i = 0; i < nums.length; i++) {
/*是为了解决[1,-2147483648,2]这个测试实例本身就包含min,但是后面判断逻辑没有走进count++
* 从而返回了first:2
* */
if(nums[i] == Integer.MIN_VALUE && flag){
count++; //只是count++,并不影响未出现前的first,second,third
flag = false; //之后再有重复出现的Integer.MIN_VALUE便不再处理,走最后一个else分支
}
if(nums[i] > first){
count++;
third = second;
second = first;
first = nums[i];
}else if((nums[i] > second) && (nums[i] < first)){ //注意这里不能加等号,是为了防止重复元素的干扰
count++;
third = second;
second = nums[i];
}else if((nums[i] > third) && (nums[i] < second)){
count++;
third = nums[i];
}else {
continue;
}
}
if(count < 3) {
return first;
}
return third;
}
}
运行结果如下
3.treeset集合(执行效率不是很高,但易于理解)
treeset可以实现去重,并能保证默认从小到大的顺序
java代码如下
public int thirdMax1(int[] nums) {
TreeSet<Integer> set = new TreeSet<>();
for (int i = 0; i < nums.length; i++) {
set.add(nums[i]); //在添加的过程中自动去重
}
if(set.size()<3) {
return set.last();
}else {
set.pollLast();
set.pollLast();
return set.last();
}
}
下一篇: LeetCode213——打家劫舍II