C++ linked list + unordered_map solution


  • 0
    A

    If we treat the access time of unordered_map and unordered_set as O(1) (though strictly speaking, they are not O(1), as the worst case can deteriorate to O(n), but rarely), then every function is O(1) time.

    14 / 14 test cases passed
    Status: Accepted
    Runtime: 79 ms

    class AllOne {
    protected:
        string nil;
        list<pair<uint, unordered_set<const string*>>> lst; // use pointer to save time and space
        unordered_map<string, list<pair<uint, unordered_set<const string*>>>::iterator> map;
    public:
        AllOne() {
            lst.emplace_back(0, unordered_set<const string*>());
            lst.begin()->second.insert(&nil);
        }
    
        void inc(string key) {
            list<pair<uint, unordered_set<const string*>>>::iterator iter = ++lst.begin();
            uint val = 1;
            auto it = map.find(key);
            if (it != map.end()) {
                iter = it->second;
                val = iter->first + 1;
                iter->second.erase(&it->first);
                if (!iter->second.size()) iter = lst.erase(iter);
                else iter++;
            }
            if (iter == lst.end() || iter->first != val) iter = lst.insert(iter, pair<uint, unordered_set<const string*>>(val, unordered_set<const string*>()));
            map[key] = iter;
            iter->second.insert(&map.find(key)->first);
        }
    
        void dec(string key) {
            auto it = map.find(key);
            if (it == map.end()) return;
            list<pair<uint, unordered_set<const string*>>>::iterator& iter = it->second; // reference
            uint val = iter->first - 1;
            iter->second.erase(&it->first);
            if (!iter->second.size()) iter = lst.erase(iter);
            if (!val) map.erase(key);
            else {
                if (prev(iter)->first != val) iter = lst.insert(iter, pair<uint, unordered_set<const string*>>(val, unordered_set<const string*>()));
                else iter--;
                iter->second.insert(&it->first);
            }
        }
    
        string getMaxKey() {
            return **lst.rbegin()->second.begin();
        }
    
        string getMinKey() {
            return lst.size() > 1 ? **(++lst.begin())->second.begin() : **lst.begin()->second.begin();
        }
    };
    

Log in to reply
 

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