相关问题：146. LRU Cache
问题：
设计类LFUCache，实现LFU Cache
Least Frequently Used
优先度为：访问频率最多优先 的缓存。
Example 1:
Input
["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]
Explanation
// cnt(x) = the use counter for key x
// cache=[] will show the last used order for tiebreakers (leftmost element is most recent)
LFUCache lfu = new LFUCache(2);
lfu.put(1, 1); // cache=[1,_], cnt(1)=1
lfu.put(2, 2); // cache=[2,1], cnt(2)=1, cnt(1)=1
lfu.get(1); // return 1
// cache=[1,2], cnt(2)=1, cnt(1)=2
lfu.put(3, 3); // 2 is the LFU key because cnt(2)=1 is the smallest, invalidate 2.
// cache=[3,1], cnt(3)=1, cnt(1)=2
lfu.get(2); // return -1 (not found)
lfu.get(3); // return 3
// cache=[3,1], cnt(3)=2, cnt(1)=2
lfu.put(4, 4); // Both 1 and 3 have the same cnt, but 1 is LRU, invalidate 1.
// cache=[4,3], cnt(4)=1, cnt(3)=2
lfu.get(1); // return -1 (not found)
lfu.get(3); // return 3
// cache=[3,4], cnt(4)=1, cnt(3)=3
lfu.get(4); // return 4
// cache=[3,4], cnt(4)=2, cnt(3)=3
Constraints:
0 <= capacity, key, value <= 10^4
At most 10^5 calls will be made to get and put.
解法：LFU
c++中 利用 map 和 unordered_map 来实现：
那么，对于cache，我们有以下两个基本操作：
再看题目所求：
代码参考：
1 class LFUCache { 2 public: 3 LFUCache(int capacity) { 4 size = capacity; 5 } 6 7 int get(int key) { 8 //cout<<"get:"<<key<<endl; 9 if(kv.count(key)) { 10 update(key, kv[key]); 11 return kv[key]; 12 } 13 return -1; 14 } 15 16 void put(int key, int value) { 17 //cout<<"put:"<<key<<"= "<<value<<endl; 18 if(!kv.count(key) && kv.size()==size) { 19 //cout<<"outlast"<<endl; 20 if(false==outlast()) return; 21 } 22 update(key, value); 23 return; 24 } 25 private: 26 int size; 27 map<int, list<int>> cache;//frequency: key list(oldest->back; new->begin) 28 unordered_map<int, int> kv;//key:value 29 unordered_map<int, pair<int, list<int>::iterator>> kf;//key:frequency,idx 30 void update(int key, int value) { 31 if(kv.count(key)) {//exist 32 cache[kf[key].first].erase(kf[key].second); 33 if(cache[kf[key].first].empty()) cache.erase(kf[key].first); 34 } 35 kv[key] = value; 36 kf[key].first++; 37 cache[kf[key].first].push_front(key); 38 kf[key].second = cache[kf[key].first].begin(); 39 } 40 bool outlast() { 41 if(cache.empty()) return false; 42 int last = cache.begin()->second.back();//cache.begin->minimal frequency 43 //cout<<"out:"<<last<<endl; 44 cache.begin()->second.pop_back(); 45 if(cache.begin()->second.empty()) cache.erase(cache.begin()); 46 kv.erase(last); 47 kf.erase(last); 48 return true; 49 } 50 }; 51 52 /** 53 * Your LFUCache object will be instantiated and called as such: 54 * LFUCache* obj = new LFUCache(capacity); 55 * int param_1 = obj->get(key); 56 * obj->put(key,value); 57 */
原文：https://www.cnblogs.com/habibah-chang/p/14661854.html