414. Third Maximum Number

1，题目要求
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).

找到一个数组中第三大的数，如果不存在就返回最大的数。

2，题目思路
找到第三大的数字，利用有序的数列是比较好的办法。首先，重复的数字是需要处理的。如果用直接对nums进行排序然后逐个判断的办法，还需要对这样的重复的情况来进行单独的处理，比较麻烦。
因此，可以利用C++自带的容器中的自动排序的办法：set
set不仅可以在插入新元素时，按照从小到大的顺序的来进行安排，而且还可以去除重复的元素。
定义一个这样的set，依次将nums中的数字加入到其中的同时也保证其中的数字的个数不会超过3个：当其中的数字的个数为4个时，就将第一个数字（最小的那个）删除。
在最后，如果set中的元素的个数为3，则直接返回第一个元素即可；否则就返回最后一个元素（最大的）。

3，程序源码

class Solution {
public:
    int thirdMax(vector<int>& nums) {
        set<int> top3;
        for(auto n : nums)
        {
            top3.insert(n);
            if(top3.size() == 4)
                top3.erase(top3.begin());
        }

        if(top3.size() == 3)    return *top3.begin();
        else    return*top3.rbegin();
    }
};

注：

• c.begin() 返回一个迭代器，它指向容器c的第一个元素；

• c.end() 返回一个迭代器，它指向容器c的最后一个元素的下一个位置；

• c.rbegin() 返回一个逆序迭代器，它指向容器c的最后一个元素；

• c.rend() 返回一个逆序迭代器，它指向容器c的第一个元素前面的位置；

• 迭代器实际上是一个指针，取值的话还是要按照指针的操作方式来做。