Trying to use vector instead of list but failed..


  • 0
    V

    I tried to use vector instead of list as in other solutions but met some really weird error:

    class LFUCache {
        int cap;
        int size;
        int minFreq;
        unordered_map<int, pair<int, int>> m; //key to {value,freq};
        unordered_map<int, vector<int>::iterator> mIter; //key to list iterator;
        unordered_map<int, vector<int>>  fm;  //freq to key list;
    public:
        LFUCache(int capacity) {
            cap=capacity;
            size=0;
        }
        
        int get(int key) {
            if(m.count(key)==0) return -1;
            fm[m[key].second].erase(mIter[key]);
            m[key].second++;
            cout<<"key is: "<<m[key].second<<endl;
            if (fm.count((m[key].second)) == 0) {
                cout<<"inside"<<endl;
                fm[m[key].second] = vector<int>();
            }
            cout<<"outside"<<endl;
            fm[m[key].second].push_back(key);
            mIter[key]=(fm[m[key].second].end()) - 1;
            if(fm[minFreq].size()==0 ) 
                  minFreq++;
            
            return m[key].first;
        }
        
       void put(int key, int value) {
            if(cap<=0) return;
            
            int storedValue=get(key);
            if(storedValue!=-1)
            {
                m[key].first=value;
                return;
            }
            
            if(size>=cap )
            {
                m.erase( fm[minFreq].front() );
                mIter.erase( fm[minFreq].front() );
                fm[minFreq].erase(fm[minFreq].begin());
                size--;
            }
            m[key]={value, 1};
            if (fm.count(1) == 0) {
                fm[1] = vector<int>();
            }
            fm[1].push_back(key);
            mIter[key]=fm[1].end() - 1;
            minFreq=1;
            size++;
        }
    };
    
    /**
     * Your LFUCache object will be instantiated and called as such:
     * LFUCache obj = new LFUCache(capacity);
     * int param_1 = obj.get(key);
     * obj.put(key,value);
     */
    

    I used the testcase:
    ["LFUCache","put","put","put","put"]
    [[4],[1,1],[2,2],[1, 1],[3,3]]

    But got runtime error and the stdout:

    Stdout:
    key is: 2
    

    The "inside" and "outside" are not printed at all. Did I make any stupid mistake here...?


  • 0
    V

    This also doesn't work. Confused. Why we must use list iterator? What's the trick here?

    class LFUCache {
        int cap;
        int size;
        int minFreq;
        unordered_map<int, pair<int, int>> m; //key to {value,freq};
        unordered_map<int, int> mIter; //key to vector index;
        unordered_map<int, vector<int>>  fm;  //freq to key list;
    public:
        LFUCache(int capacity) {
            cap=capacity;
            size=0;
        }
        
        int get(int key) {
            if(m.count(key)==0) return -1;
            fm[m[key].second].erase(fm[m[key].second].begin() + mIter[key]);
            m[key].second++;
            fm[m[key].second].push_back(key);
            mIter[key]=fm[m[key].second].size() - 1;
            
            if(fm[minFreq].size()==0 ) 
                  minFreq++;
            
            return m[key].first;
        }
        
       void put(int key, int value) {
            if(cap<=0) return;
            
            int storedValue=get(key);
            if(storedValue!=-1)
            {
                m[key].first=value;
                return;
            }
            
            if(size>=cap )
            {
                m.erase( fm[minFreq].front() );
                mIter.erase( fm[minFreq].front() );
                fm[minFreq].erase(fm[minFreq].begin());
                size--;
            }
            
            m[key]={value, 1};
            fm[1].push_back(key);
            mIter[key]=fm[1].size() - 1;
            minFreq=1;
            size++;
        }
    };
    
    /**
     * Your LFUCache object will be instantiated and called as such:
     * LFUCache obj = new LFUCache(capacity);
     * int param_1 = obj.get(key);
     * obj.put(key,value);
     */
    

Log in to reply
 

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