关关的刷题日记13 – 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.

题目的意思是给定一个非空数组，要求返回第三大的数，如果不存在的话，就返回最大的数。要求实现复杂度为O(n)。而且要注意从给出的例子可以看出，第三大的数必须是第三个不重复的数。

思路

分析：拿出这道题首先想到的思路是排序，直接找出最大的和第三大的数，但是不满足复杂度要求。所以直接遍历一遍该数组，一次性找出最大、第二大、第三大的三个数，思路同遍历一遍数组直接找出最大的数一样。有个坑要注意，就是给定输入中，有可能最小值就是INT_MIN，所以我们用的long，初始化设置为LONG_MIN.

class Solution {
public:
    int thirdMax(vector<int>& nums) {
    long max=LONG_MIN, second=LONG_MIN, third=LONG_MIN;
        for(int i=0; i<nums.size(); i++)
        {
            if(nums[i]>max)
            {
                third=second;
                second=max;
                max=nums[i];
            }
            else if(nums[i]>second && nums[i]!=max)
            {
                third=second;
                second=nums[i];
            }
            else if(nums[i]>third && nums[i]!=second && nums[i]!=max)
            {
                third=nums[i];
            }
        }
        return (third==LONG_MIN?max:third);
    }
};

人生易老，唯有陪伴最长情，加油！

以上就是关关关于这道题的总结经验，希望大家能够理解，有什么问题可以在我们的专知公众号平台上交流或者加我们的QQ专知-人工智能交流群 426491390，也可以加入专知——Leetcode刷题交流群（请先加微信小助手weixinhao: Rancho_Fang）。 同时请，关注我们的公众号，获取最新关于专知以及人工智能的资讯、技术、算法等内容。扫一扫下方关注我们的微信公众号。