Share my O(1) solution with 2 hashtables and 1 linkedlist;


  • 0
    B
    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 (mTable.count(key) > 0) {    //exists;
                MyList::iterator it_to_remove = mTable[key];
                int old_val = it_to_remove->second;
                int new_val = old_val + 1; 
                //insert new.
                if (mValueTable.count(new_val) > 0) {
                    MyList::iterator it = mList.insert(++mValueTable[new_val].second, make_pair(key, new_val));
                    mValueTable[new_val].second = it;
                    mTable[key] = it;
                } else {    //if no new val insertion position in list, use the end it of old val's
                    MyList::iterator it = mValueTable[old_val].second;
                    it = mList.insert(++it, make_pair(key, new_val));
                    mValueTable[new_val] = make_pair(it, it);
                    mTable[key] = it;
                }
                //remove
                removeListByIter(it_to_remove);
            } else {    //doesn't exist.
                mList.insert(mList.begin(), make_pair(key, 1));
                //in no value 1 in table, use iterator_begin;
                if (mValueTable.find(1) == mValueTable.end()) {
                    mValueTable[1] = make_pair(mList.begin(), mList.begin());
                } else {
                    mValueTable[1].first = mList.begin();
                }
                mTable[key] = mList.begin();
            }
        }
        
        /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
        void dec(string key) { 
            if (mTable.count(key) > 0) {
                MyList::iterator it_to_remove = mTable[key];
                int old_val = it_to_remove->second;
                int new_val = old_val - 1;
                if (new_val > 0) {
                    if (mValueTable.count(new_val) > 0) {
                        MyList::iterator it = mList.insert(++mValueTable[new_val].second, make_pair(key, new_val));
                        mValueTable[new_val].second = it;
                        mTable[key] = it;
                    } else {    
                        MyList::iterator it = mValueTable[old_val].first;
                        it = mList.insert(it, make_pair(key, new_val));
                        mValueTable[new_val] = make_pair(it, it);
                        mTable[key] = it;
                    }
                } else {
                    mTable.erase(key);
                }
                //remove old;
                removeListByIter(it_to_remove);
            }
        }
        
        /** Returns one of the keys with maximal value. */
        string getMaxKey() {
            if (mList.empty()) {
                return "";
            }
            return mList.back().first;
        }
        
        /** Returns one of the keys with Minimal value. */
        string getMinKey() {
            if (mList.empty()) {
                return "";
            }
            return mList.front().first;
        }
    private:
    
        typedef list<pair<string, int>> MyList;
        unordered_map<string, MyList::iterator> mTable; 
        MyList mList;
        unordered_map<int, pair<MyList::iterator, MyList::iterator>> mValueTable;   
        void removeListByIter(MyList::iterator it_to_remove) {
            int old_val = it_to_remove->second;
            MyList::iterator it_start = mValueTable[old_val].first;
            MyList::iterator it_end = mValueTable[old_val].second;
            if (it_start == it_to_remove && it_end == it_start) {
                mValueTable.erase(old_val);
            } else if (it_start == it_to_remove) {
                ++mValueTable[old_val].first;
            } else if (it_end == it_to_remove) {
                --mValueTable[old_val].second;
            }
            mList.erase(it_to_remove);
        }
    };
    
    /**
     * Your AllOne object will be instantiated and called as such:
     * AllOne obj = new AllOne();
     * obj.inc(key);
     * obj.dec(key);
     * string param_3 = obj.getMaxKey();
     * string param_4 = obj.getMinKey();
     * 
     */
    

    mTable stores <key, iterator>
    mValueTable stores <value, <begin iterator, end iterator>>
    mList is a linked list of <key, val>


Log in to reply
 

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