[LeetCode]414. Third Maximum Number

题目描述

思路

map可解，开始的思路是o(n)空间
参考答案，可以用o(1)空间的解法

代码

#include <iostream>
#include <map>
#include <set>
#include <vector>

using namespace std;

class Solution {
public:
    int thirdMax(vector<int>& nums) {
        /*
        map<int, int> m;
        for (int num : nums)
            m[num]++;
        int cur_count = 3;
        for (auto iter = m.rbegin(); iter != m.rend(); iter++) {
            cur_count--;
            if (cur_count == 0) return iter->first;
        }

        if (cur_count > 0)
            return m.rbegin()->first;
        */

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

int main() {
    vector<int> nums = { 3, 2,2,2,2,2, 1 };
    Solution s;

    cout << s.thirdMax(nums) << endl;

    system("pause");
    return 0;
}