Third Maximum Number解题报告

Description:

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:

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.

Link:

https://leetcode.com/problems/third-maximum-number/#/description

解题方法：

用三个数分别储存第一、第二、第三大的数，当出现等于这三个数的情况，不进行更新。

Tips:

为了防止数组中有INT_MIN，用long来储存，这样初始化为比INT_MIN还小的数，最后就可以知道第三大的数有没有更新。

Time Complexity：

O(N)

完整代码：

int thirdMax(vector<int>& nums) 
    {
        long max1 = (long)INT_MIN - 1, max2 = (long)INT_MIN - 1, max3 = (long)INT_MIN - 1;
        for(int i: nums)
        {
            if(i == max1 || i == max2 || i == max3)
                continue;
            if(i > max1)
            {
                max3 = max2;
                max2 = max1;
                max1 = i;
            }
            else
                if(i > max2)
                {
                    max3 = max2;
                    max2 = i;
                }
                else
                    if(i > max3)
                        max3 = i;      
        }
        return max3 == (long)INT_MIN - 1 ? max1 : max3;
    }