Same to LFU cache (detailed LFU comments)


  • 0
    L

    I see this one similar to LFU cache. The value is the frequency in LFU;

    check my detailed explanation of LFU data structure

    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 (keyvals.find(key) == keyvals.end()) {// add a new key
                keyvals[key]=1;
                auto rtn = vals[1].insert(key);
                //itor[key] = rtn.first;
            } else {
                int val = keyvals[key];
                vals[val].erase(key);
                if (vals[val].empty()) vals.erase(val);
                val++;
                auto rtn = vals[val].insert(key);
                //itor[key] = rtn.first;
                keyvals[key]=val;
            }
        }
        
        /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
        void dec(string key) {
            if (keyvals.find(key) == keyvals.end()) return;
            int val = keyvals[key];
            vals[val].erase(key);
            if (vals[val].empty()) vals.erase(val);
            if (val == 1) {
                keyvals.erase(key);
                //itor.erase(key);
            } else {
                val--;
                auto rtn = vals[val].insert(key);
                //itor[key] = rtn.first;
                keyvals[key] = val;
            }
        }
        
        /** Returns one of the keys with maximal value. */
        string getMaxKey() {
            return vals.empty() ? "" : *((vals.rbegin()->second).begin());
        }
        
        /** Returns one of the keys with Minimal value. */
        string getMinKey() {
            return vals.empty() ? "" : *((vals.begin()->second).begin());
        }
    private:
        unordered_map<string, int> keyvals;
        //unordered_map<string, set<string>::iterator> itor;
        map<int, set<string> > vals;
    };
    
    /**
     * 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();
     */
    

Log in to reply
 

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