third-maximum-number

Third Maximum Number – LeetCode 414

Problem

Description

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).

Answer

Original

Code

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();
    }
};

思路

使用set的自动排序特性构造一个大小最大为3的滑动窗口。时间复杂度$O(n)$，空间复杂度$O(1)$。
耗时$9$ ms，排名$85.28\%$

Better

思路

还没看到更好的思路。