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++;    }};