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.
这道题让我们求数组中第三大的数，如果不存在的话那么就返回最大的数，题目中说明了这里的第三大不能和第二大相同，必须是严格的小于，而并非小于等于。这道题并不是很难，如果知道怎么求第二大的数，那么求第三大的数的思路都是一样的。那么我们用三个变量first, second, third来分别保存第一大，第二大，和第三大的数，然后我们遍历数组，如果遍历到的数字大于当前第一大的数first，那么三个变量各自错位赋值，如果当前数字大于second，小于first，那么就更新second和third，如果当前数字大于third，小于second，那就只更新third，注意这里有个坑，就是初始化要用长整型long的最小值，否则当数组中有INT_MIN存在时，程序就不知道该返回INT_MIN还是最大值first了，参见代码如下：
解法一：
class Solution {
public:
int thirdMax(vector<int>& nums) {
long first = LONG_MIN, second = LONG_MIN, third = LONG_MIN;
for (int num : nums) {
if (num > first) {
third = second;
second = first;
first = num;
} else if (num > second && num < first) {
third = second;
second = num;
} else if (num > third && num < second) {
third = num;
}
}
return (third == LONG_MIN || third == second) ? first : third;
}
};
下面这种方法的时间复杂度是O(nlgn)，不符合题目要求，纯粹是拓宽下思路哈，利用了set的自动排序和自动去重复项的特性，很好的解决了问题，对于遍历到的数字，加入set中，重复项就自动去掉了，如果此时set大小大于3个了，那么我们把set的第一个元素去掉，也就是将第四大的数字去掉，那么就可以看出set始终维护的是最大的三个不同的数字，最后遍历结束后，我们看set的大小是否为3，是的话就返回首元素，不是的话就返回尾元素，参见代码如下：
解法二：
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();
}
};
参考资料：
https://discuss.leetcode.com/topic/63903/short-easy-c-using-set
LeetCode All in One 题目讲解汇总(持续更新中…)
转载请注明来源于 Grandyang 的博客 (grandyang.com)，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 grandyang@qq.com
