关关的刷题日记13——Leetcode 414. Third Maximum Number

关小刷刷题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: 1Explanation: The third maximum is 1.

Example 2:Input: [1, 2]Output: 2Explanation: The third maximum does not exist, so the maximum (2) is returned instead.

Example 3:Input: [2, 2, 3, 1]Output: 1Explanation: 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);
    }
};