C++ Solution O(n)


  • 0
    J

    Iterate the input vector and using a 3-element ordered set (descending order) to keep the most 3 maximal values.

    For each element in input vector, update that ordered set. Return the third one in ordered set, or the first one (which is the max value) if there is no third max value. replicated value can be ignored by the nature of set.

    The time complexity is O(n), while the space of ordered vector only takes 4 element at most.

    ...
    void update_sort(set<int, std::greater<int>>& sorting, int in, int *max3) {
    set<int>::iterator iter;
    if (sorting.size() < 3 || ((sorting.size() >= 3 && in > *max3))) {
    sorting.insert(in);
    iter = sorting.begin();
    if (sorting.size() >= 3) {
    iter ++;
    iter ++;
    *max3 = *iter;
    if (sorting.size() > 3) {
    iter++;
    sorting.erase(iter);
    }
    }
    }
    }

    int thirdMax(vector<int>& nums) {
        set<int, std::greater<int>> sorting;
        vector<int>::iterator iter = nums.begin();
        set<int>::iterator s_ite;
        int max3;
        while (iter != nums.end()) {
            update_sort(sorting, *iter, &max3);
            iter++;
        }
        
        if (sorting.size() < 3) {
            s_ite = sorting.begin();
            return *s_ite;
        } else {
            return max3;
        }
    }
    

    ...


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.