C++ O(1) 0ms AC Solution


  • 0
    class AllOne {
    public:
        /** Initialize your data structure here. */
        AllOne() {
        }
    
        /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
        void inc(string key) {
            if (iters.find(key) == iters.end()) {
                if (ones.empty() || ones.begin()->first != 1) ones.insert(ones.begin(), make_pair(1, KeySet()));
                ones.begin()->second.insert(key);
                iters[key] = ones.begin();
            }
            else {
                Ones::iterator it, next;
                it = next = iters[key];
                next++;
                if (next != ones.end() && next->first == it->first + 1) next->second.insert(key);
                else next = ones.insert(next, make_pair(iters[key]->first + 1, KeySet({ key })));
                iters[key] = next;
                it->second.erase(key);
                if (it->second.empty()) ones.erase(it);
            }
        }
    
        /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
        void dec(string key) {
            if (iters.find(key) != iters.end()) {
                Ones::iterator it, prev;
                prev = it = iters[key];
                if (it != ones.begin()) prev--;
                if (it->first != 1) {
                    if (it == ones.begin() || prev->first != it->first - 1) 
                        prev = ones.insert(it, make_pair(iters[key]->first - 1, KeySet()));
                    prev->second.insert(key);
                    iters[key] = prev;
                }
                else iters.erase(key);
                it->second.erase(key);
                if (it->second.empty()) ones.erase(it);
            }
        }
    
        /** Returns one of the keys with maximal value. */
        string getMaxKey() {
            return ones.empty() ? "" : *ones.rbegin()->second.begin();
        }
    
        /** Returns one of the keys with Minimal value. */
        string getMinKey() {
            return ones.empty() ? "" : *ones.begin()->second.begin();
        }
    private:
        typedef unordered_set<string> KeySet;
        typedef list<pair<int, KeySet>> Ones;
        Ones ones;
        unordered_map<string, Ones::iterator> iters;
    };
    

  • 1

    getMaxKey could be like getMinKey, just with ones.rbegin instead of ones.begin.


  • 0

    @StefanPochmann
    Thank you so much. I have changed it to rbegin()


  • 1

    About your dec:

    • Where do you check whether the key exists? Is !ones.empty() a mistake?
    • If the key's value is 1, you don't remove it from iters, do you?

  • 0
    T

    I don`t think the Complexity of inc and dec are O(1) because they use unordered_set::erase which is O(n)


  • 0

    @StefanPochmann

    Thank you so much for pointing out.
    I add an else statement else iters.erase(key); to remove keys from iters if the key's value is 1.


  • 0

    @Ren.W I see you did some other changes as well. I wrote my own C++ solution yesterday, interesting to see how similar our codes ended up.

    Yours is wrong now, though, you fail for example:

    Input:
    ["AllOne","inc","inc","inc","inc","inc","dec","dec","getMaxKey","getMinKey"]
    [[],["a"],["b"],["b"],["b"],["b"],["b"],["b"],[],[]]
    
    Your answer:
    [null,null,null,null,null,null,null,null,"a","a"]
    

    Max should be "b", because its value is 2 while "a" only has value 1. Problem is that your first dec turns a=1, b=4 into a=1, b=1 instead of a=1, b=3.

    @1337c0d3r can you add this test case? And fix the C++ judge, because the expected answer is also wrong.


  • 0

    @StefanPochmann Thanks, just added this test case and fixed the C++ solution.


  • 0

    @StefanPochmann
    I guess I have fixed the bug :)
    Thank you very much for your comments.


Log in to reply
 

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