【leetcode】414. Third Maximum Number

发表于

描述
返回第三大的数

样例

1
2
输入: [1,2,2,3]
输出: 1

思路
<(￣︶￣)↗[GO!],这个题目好简单啊!排序完，再调用一下unique就ok了。然而效率是硬伤。

我的解法

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int thirdMax(vector<int>& nums) {
        sort(nums.begin(), nums.end(),greater<int>());
        if (nums.size() < 3) { return nums[0]; }
        auto uend = unique(nums.begin(), nums.end());
        if (uend - nums.begin() < 3) { return nums[0]; }
        return nums[2];
    }
};

另一个解法

set的运用，消除重复值
set与vector的区别:首先，vector是序列式容器而set是关联式容器。set包含0个或多个不重复不排序的元素。也就是说set能够保证它里面所有的元素都是不重复的。另外对set容器进行插入时可以指定插入位置或者不指定插入位置。如insert(v.begin(),1),也可以直接用insert(1)。
set默认从小到大排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int thirdMax(vector<int> & nums) {
        set<int> numsets;
        for (int n : nums) {
            numsets.insert(n);
            if (numsets.size() > 3) {
                numsets.erase(numsets.begin());
            }
        }
        return numsets.size() >= 3 ?  *numsets.begin() : *numsets.rbegin();
    }
};

参考资料
原题