leetcode 460. LFU Cache

﹏ヽ暗。殇╰゛Y 2022-06-04 10:26 100阅读 0赞

Design and implement a data structure for Least Frequently Used (LFU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.  
put(key, value) - Set or insert the value if the key is not already present. When the cache reaches its capacity, it should invalidate the least frequently used item before inserting a new item. For the purpose of this problem, when there is a tie (i.e., two or more keys that have the same frequency), the least recently used key would be evicted.

Follow up:  
Could you do both operations in O(1) time complexity?

Example:

LFUCache cache = new LFUCache( 2 /\* capacity \*/ );

cache.put(1, 1);  
cache.put(2, 2);  
cache.get(1); // returns 1  
cache.put(3, 3); // evicts key 2  
cache.get(2); // returns -1 (not found)  
cache.get(3); // returns 3.  
cache.put(4, 4); // evicts key 1.  
cache.get(1); // returns -1 (not found)  
cache.get(3); // returns 3  
cache.get(4); // returns 4

不喜欢这样的题，答案是参考网上的答案，就这么做吧

代码如下：

class LFUCache 
    {
       int size;
       int minfreq;
       int cap;
       map<int,pair<int,int>> m;//key to pair<value,freq>
       map<int,list<int>::iterator> mIter;//key to list location
       map<int,list<int>> fm;//freq to 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]);//删除key在fm原来的位置
           m[key].second++;//频率加一
           fm[m[key].second].push_back(key);//按照频率，放在新的位置上
           mIter[key]=--fm[m[key].second].end();//存储key现在所在的链表例=里的位置
           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)//可能要根据LFU删掉一个元素
          {
              m.erase(fm[minfreq].front());
              mIter.erase(fm[minfreq].front());
              fm[minfreq].pop_front();
              size--;
          }
          m[key]={value,1};
          fm[1].push_back(key);
          mIter[key]=--fm[1].end();
          minfreq=1;
          size++;
        }
    };