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. 题意寻找一个数组中第三大的数，如果不存在返回最大的数。 直接的做法就是排序，查找第三个即可，C++实现如下

int thirdMax(vector
     
      & nums) {        sort(nums.begin(),nums.end());        int count=1;        for(int i=nums.size()-1;i>0;i--)        {            if(nums[i]!=nums[i-1])                count++;            if(count==3)                return nums[--i];        }        return nums[nums.size()-1];    }
     

　也可以利用set集合的有序性和唯一性，C++实现如下

int thirdMax(vector
     
      & nums) {        set
      
        t_set;        for(auto &i:nums)            t_set.insert(i);        auto r_iter=t_set.rbegin();        if(t_set.size()<3)            return *r_iter;        r_iter++;        r_iter++;        return *r_iter;    }