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)以内。

理  解：

　　用set存放数据，不出现重复的数字。且内部从小到大排序。set大小小于3，则返回最大的数。set大小大于等于3，则返回倒数第三个数。

　　或者 ： 直接遍历保存第一、第二、第三大的数。

代 码 C++：

class Solution {
public:
    int thirdMax(vector<int>& nums) {
        set<int> sortNums(nums.begin(),nums.end());
        set<int>::iterator itr = sortNums.end();
        
        if(sortNums.size()<3)
            return *prev(itr,1);
        else
            return *prev(itr,3);
    }
};

运行结果：

　　执行用时 :20 ms, 在所有 C++ 提交中击败了35.10%的用户

　　内存消耗 :10.4 MB, 在所有 C++ 提交中击败了19.73%的用户