460. LFU Cache

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 1cache.put(3, 3);    // evicts key 2cache.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 3cache.get(4);       // returns 4
转载于点击打开链接
要求所有的操作都在O(1)的时间内完成，因为涉及到插入删除，链表优先。
把所有具有相同频率的关键字存放在一个链表上，方便删除频率最低最近最少使用的关键字。
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 listpublic:    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++;    }};