题目
给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数。
示例 1：
输入：[3, 2, 1] 输出：1 解释：第三大的数是 1 。
示例 2：
输入：[1, 2] 输出：2 解释：第三大的数不存在, 所以返回最大的数 2 。
示例 3：
输入：[2, 2, 3, 1] 输出：1 解释：注意，要求返回第三大的数，是指在所有不同数字中排第三大的数。 此例中存在两个值为 2 的数，它们都排第二。在所有不同数字中排第三大的数为 1 。
解题
方法一：一次遍历
class Solution { public: int thirdMax(vector<int>& nums) { sort(nums.begin(),nums.end(),greater<>()); //从大到小排序 for(int i=0,index=0;i<nums.size();i++){//index代表第index个不同的数 if(i>0&&nums[i]==nums[i-1]) continue; //把重复的continue index++; if(index==3) return nums[i]; //取到第三大的 } return nums[0]; //遍历结束后，还没return，说明没有取到第三大的，于是返回最大的 } };
复杂度O(nlogn) ，因为排序需要nlogn复杂度.
方法二：有序集合
我们可以遍历数组，同时用一个有序集合来维护数组中前三大的数
使用有序集合set, 默认是从小到大排的，所以当集合大小为3的时候返回*s.begin(),代表第三大的数，集合大小不为3的时候换回末尾*s.rbegin(),代表最大的数
class Solution { public: int thirdMax(vector<int>& nums) { set<int> s; for(int num:nums){ s.insert(num); if(s.size()>3){ s.erase(s.begin()); } } return s.size()==3?*s.begin():*s.rbegin(); } };
