专栏首页chenjx85的技术专栏leetcode-414-Third Maximum Number

leetcode-414-Third Maximum Number

题目描述:

Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).

Example 1:

Input: [3, 2, 1]

Output: 1

Explanation: The third maximum is 1.

Example 2:

Input: [1, 2]

Output: 2

Explanation: The third maximum does not exist, so the maximum (2) is returned instead.

Example 3:

Input: [2, 2, 3, 1]

Output: 1

Explanation: Note that the third maximum here means the third maximum distinct number.
Both numbers with value 2 are both considered as second maximum.

要完成的函数:

int thirdMax(vector<int>& nums) 

说明:

1、这道题目题意清晰,返回给定vector中的第三大的数值,如果没有第三大的数,那么返回最大的数。重复的数算一个,比如[2,2,3,1],2算是第二大的数,1是第三大的数。要求O(n)的时间复杂度

2、解法一:

没有要求空间复杂度,只是要求时间复杂度为O(n),那么我们可以定义三个整数,用来存放最大的整数,第二大的整数,第三大的整数。

然后对vector做一次遍历,如果比max1大,那么更新max1、max2、max3;如果比max1小但比max2大,那么更新max2、max3;如果只比max3大,那么更新max3;如果都不比这三个数大,那么处理下一个数。

那么max1、max2、max3的初始值应该是多少呢?

我们可以把它们设置为INT_MAX,这样子无论最开始是什么数,这三个数都会更新。

代码如下:

    int thirdMax(vector<int>& nums) 
    {
        int max1=INT_MIN,max2=INT_MIN,max3=INT_MIN;
        for(int i=0;i<nums.size();i++)
        {if(nums[i]==max1||nums[i]==max2||nums[i]==max3)//如果出现重复的数
            {
                continue;
            }
            if(nums[i]>max1)
            {
                max3=max2;
                max2=max1;
                max1=nums[i];
            }
            else if(nums[i]>max2)
            {
                max3=max2;
                max2=nums[i];
            }
            else if(nums[i]>max3)
            {
                max3=nums[i];
            }
        }
    }

上述代码还没有处理边界情况,也就是当vector中没有三个及三个以上不重复元素的时候,我们应该输出max1。

那么如何判断vector中有没有出现?当没有出现的时候,我们发现max3为INT_MIN。似乎可以用这个作为判断条件。

但是如果vector中有三个元素,其中一个为INT_MIN呢?我们不能用max3==INT_MIN来说明,max3没被修改过,即vector中没有三个及三个以上不重复元素。

那我们再细致地考虑下,修改代码如下:

    int thirdMax(vector<int>& nums) 
    {
        int max1=INT_MIN,max2=INT_MIN,max3=INT_MIN,count=0;
        for(int i=0;i<nums.size();i++)
        {
            if(nums[i]==INT_MIN)//判断vector中有没有出现INT_MIN
                count++;
            if(nums[i]==max1||nums[i]==max2||nums[i]==max3)
                continue;
            if(nums[i]>max1)
            {
                max3=max2;
                max2=max1;
                max1=nums[i];
            }
            else if(nums[i]>max2)
            {
                max3=max2;
                max2=nums[i];
            }
            else if(nums[i]>max3)
            {
                max3=nums[i];
            }
        }
        if(max3==INT_MIN)
        {
            if(count==0)//如果没有出现INT_MIN在vector中,那么好办,如果max3==INT_MIN,说明根本就没有三个不重复元素
                return max1;
            else
            {
                if(max2!=INT_MIN)//如果出现了,而且max3==INT_MIN,而max2不是,那么说明有三个不重复元素
                    return max3;
                else //如果出现了,而且max3==INT_MIN,max2==INT_MIN,那么说明有两个或一个不重复元素
                    return max1;
            }
        }
        return max3;
    }

这种做法略微繁琐,实测8ms,beats 84.33% of cpp submissions。

3、解法二:

上述2中解法可能有些朋友会觉得麻烦,没有必要,我们把max1等这三个数改成LONG LONG的不就好了吗?那么就可以用max3是不是等于LLONG_MIN来判断是否max3有修改过,即是否有多于三个元素在vector中。

下面附上这种方法的代码:

    int thirdMax(vector<int>& nums) 
    {
        
        long long max1=LLONG_MIN,max2=LLONG_MIN,max3=LLONG_MIN;
        for(int i=0;i<nums.size();i++)
        {
            if(nums[i]==max1||nums[i]==max2||nums[i]==max3)
            {
                continue;
            }
            if(nums[i]>max1)
            {
                max3=max2;
                max2=max1;
                max1=nums[i];
            }
            else if(nums[i]>max2)
            {
                max3=max2;
                max2=nums[i];
            }
            else if(nums[i]>max3)
            {
                max3=nums[i];
            }
        }
        if(max3==LLONG_MIN)
        {
            return max1;
        }
        return max3;
    }

这种做法比起解法一,减少了琐碎的条件判断,实测7ms,beats 98.73% of cpp submissions。

4、解法三:排序

排序也可以解决这个问题,但是排序没有时间复杂度为O(n)。不过我们可以考虑部分快排。

代码如下:

    int thirdMax(vector<int>& nums) 
    {
        set<int>s1(nums.begin(),nums.end());
        vector<int>v1(s1.begin(),s1.end());
        if(v1.size()==2)
            return max(v1[0],v1[1]);
        else if(v1.size()==1)
            return v1[0];
        nth_element(v1.begin(),v1.end()-3,v1.end());
        return v1[v1.size()-3];
    }

最开始用set去掉重复元素。

nth_element是头文件algorithm中的函数,对vector进行升序快速排列,直到第二个参数,也就是上述代码中v1.end()-3停留在最终位置。这是部分快排。

这种做法多了set和vector的定义以及初始化,部分快排时间复杂度为O(n),因为只对vector做了一遍遍历。

实测12ms,beats 23.16% of cpp submissions。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode-747-Largest Number At Least Twice of Others(求vector的最大值和次大值)

    chenjx85
  • leetcode-628-Maximum Product of Three Numbers

    chenjx85
  • leetcode-697-Degree of an Array

    chenjx85
  • 『Go 语言学习专栏』-- 第四期

    谢伟
  • 微信公众号页面有效期访问设置

    页面有效期访问分为前台JS校验和后台时间校验,前台校验能够解决业务上的效果实现,而后台校验主要用于防止系统漏洞,增加系统安全性,应用场景如下:

    博文视点Broadview
  • Apache Hive Table

    这两种文件格式Hive都支持,但是有个缺点就是:用户要对文本文件中那些不需要作为分隔符处理的逗号或者制表符格外小心。

    DataScience
  • 迷恋猫CryptoKitties案例分析

    CryptoKitties别名:迷恋猫、加密猫,是Axiom Zen于2017年推出的一款基于以太坊的游戏,上线一周就受到了各种路人的追捧,上线不久后,以太坊的...

    JouyPub
  • 遍历JSON对象中的key 和 value

    跟着阿笨一起玩NET
  • JMeter: Socket Exception in high concurrent parallel request

    2017-09-01 17:03:36,542 INFO o.a.j.p.h.s.HTTPHC4Impl$3: I/O exception (java.net....

    Jerry Wang
  • Go语言sync包的应用详解

    在并发编程中同步原语也就是我们通常说的锁的主要作用是保证多个线程或者 goroutine在访问同一片内存时不会出现混乱的问题。Go语言的sync包提供了常见的并...

    KevinYan

扫码关注云+社区

领取腾讯云代金券