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

解題方法：

用三個數(shù)分別儲存第一、第二、第三大的數(shù)，當(dāng)出現(xiàn)等于這三個數(shù)的情況，不進(jìn)行更新。

Tips:

為了防止數(shù)組中有INT_MIN，用long來儲存，這樣初始化為比INT_MIN還小的數(shù)，最后就可以知道第三大的數(shù)有沒有更新。

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