460.LFU缓存

https://leetcode-cn.com/problems/lfu-cache/

与146.LRU缓存的区别在于，这里不止考虑时间，还要考虑频率，频率相同时才比较时间。

用两个简单map：keyToVal查值（put操作传入k和v），keyToFreq查频率（get操作需要增加k的频率，需要快速获取）

一个复杂map：freqToKeys，键为频率，值为相同频率的链表（使用java的LinkedHashSet），链表头就是最早加入的。删除key时，从这个map中找最小频率（用minFreq维护）对应的链表头删除，即满足题意。

注意minFreq只需要在freqToKeys表大小变化时更新，永远指向最小的key

class LFUCache {
    // 用于快速查值。简称kv
    private HashMap<Integer, Integer> keyToVal;
    // 用于快速查频率。简称kf
    private HashMap<Integer, Integer> keyToFreq;
    // 用于频率相同时删最早的，简称fk
    private HashMap<Integer, LinkedHashSet<Integer>> freqToKeys;
    // 最小频率（用于标识fk表最小的key）
    private int minFreq;
    // 容量
    private int cap;

    // 初始化
    public LFUCache(int capacity) {
        keyToVal = new HashMap<>();
        keyToFreq = new HashMap<>();
        freqToKeys = new HashMap<>();
        cap = capacity;
        minFreq = 0;
    }

    // 对外get接口
    public int get(int key) {
        if (!keyToVal.containsKey(key)) {
            return -1;
        }
        // 增加key对应的freq
        increaseFreq(key);
        return keyToVal.get(key);
    }

    // 对外put接口
    public void put(int key, int value) {
        if (this.cap == 0) return;
        if (keyToVal.containsKey(key)) {
            keyToVal.put(key, value);
            // 增加key对应的freq
            increaseFreq(key);
        } else {
            // key不存在
            // 若容量已满，需要淘汰一个
            if (this.cap <= keyToVal.size()) {
                removeMinFreqKey();
            }
            keyToVal.put(key, value);
            keyToFreq.put(key, 1);
            // 插入fk表
            // 若频率1不存在，给一个新的set；若存在则直接将key加入集合
            freqToKeys.putIfAbsent(1, new LinkedHashSet<>());
            freqToKeys.get(1).add(key);
            // 更新最小频率
            minFreq = 1;
        }
    }

    private void removeMinFreqKey() {
        // freq最小的key列表
        LinkedHashSet<Integer> keyList = freqToKeys.get(this.minFreq);
        // 列表第一个就是最早加入的key，应删除
        int delKey = keyList.iterator().next();
        // 更新fk表
        keyList.remove(delKey);
        if (keyList.isEmpty()) {
            freqToKeys.remove(minFreq);
        }
        // 此处没必要更新minFreq，因为只有put操作调用本函数，而put会将minFreq置1
        // 更新kv表和kf表
        keyToVal.remove(delKey);
        keyToFreq.remove(delKey);
    }

    private void increaseFreq(int key) {
        // 先取key的freq
        int freq = keyToFreq.get(key);
        freqToKeys.get(freq).remove(key);
        if (freqToKeys.get(freq).isEmpty()) {
            freqToKeys.remove(freq);
            if (minFreq == freq) {
                minFreq++;
            }
        }
        // 更新fk表
        // 若频率freq+1不存在，给一个新的set；若存在则直接将key加入集合
        freqToKeys.putIfAbsent(freq + 1, new LinkedHashSet<>());
        freqToKeys.get(freq + 1).add(key);
        // 更新kf表
        keyToFreq.put(key, freq + 1);
    }

    public static void main(String[] args) {
        LFUCache lFUCache = new LFUCache(0);
        lFUCache.put(0, 0);
        int a = lFUCache.get(0);
        System.out.println(a);
    }
}