参考

LeetCode算法题解：LFU Cache
LFU Cache 最近最不常用页面置换缓存器

题目要求

设计并实现一个数据结构，满足LFU (Least Frequently Used) Cache特性，实现两种操作：get和put

• get(key)：返回指定key对应的value，如果指定key在cache中不存在，返回-1
• put(key, value)：设置指定key的value，如果key不存在，则插入该key-value对。如果cache空间已满，则将最少使用的key-value对移除，如果存在多个key-value对的使用次数相同，则将上次访问时间最早的key-value对移除。

public class LFUCache {
    public LFUCache(int capacity) {}  
    public int get(int key) {}
    public void put(int key, int value) {}
}

要求O(1)的时间复杂度

思路一

O(1)的复杂度，第一想到的就是hash表。使用hash表可以O(1)时间内，获取到key-value。频次更新也可以用一个map，频次作为key，链表位置作为value，入链表的先后顺序和时间相关。

class LFUCache {
public:
    LFUCache(int capacity) {
        cap = capacity;
    }
    
    int get(int key) {
        if (m.count(key) == 0) return -1;
        freq[m[key].second].erase(iter[key]);
        ++m[key].second;
        freq[m[key].second].push_back(key);
        iter[key] = --freq[m[key].second].end();
        if (freq[minFreq].size() == 0) ++minFreq;
        return m[key].first;
    }
    
    void put(int key, int value) {
        if (cap <= 0) return;
        if (get(key) != -1) {
            m[key].first = value;
            return;
        }
        if (m.size() >= cap) {
            m.erase(freq[minFreq].front());
            iter.erase(freq[minFreq].front());
            freq[minFreq].pop_front();
        }
        m[key] = {value, 1};
        freq[1].push_back(key);
        iter[key] = --freq[1].end();
        minFreq = 1;
    }

private:
    int cap, minFreq;
    unordered_map<int, pair<int, int>> m;  // pair.first : value of data, pair.second : frequency
    unordered_map<int, list<int>> freq;  // list<int> : list for data keys, the key of map is frequency
    unordered_map<int, list<int>::iterator> iter;  // data key's position in the list, the key of map is key
};

思路二

思路一中，全部用hashmap来实现。但是没有必要使用那么多hashmap。因为频次的增加，都是+1，也就是说数据节点只需要往后移动一位，那么使用链表也可以管理频次，无序hashmap。相对而言，实现的代码会更复杂一些，但是可以减少hash的计算，理论上性能会更优。
具体可参见LeetCode算法题解：LFU Cache