欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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;
    }
}

运行结果如下

leetcode414-第三大的数

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;
    }
}

运行结果如下

leetcode414-第三大的数
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();
        }
    }

leetcode414-第三大的数

相关标签: leetcode