LeetCode : 460. LFU Cache

[congr]

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

[congr]

[congr]

class LFUCache {
    Map<Integer, Integer> valueMap;
    Map<Integer, Integer> countMap;
    Map<Integer, LinkedHashSet<Integer>> listMap;
    int capa;
    int least;

    public LFUCache(int capacity) {
        capa = capacity;
        least = -1;
        valueMap = new HashMap();
        countMap = new HashMap();
        listMap = new HashMap();
    }

    public int get(int key) {
        if (!valueMap.containsKey(key)) return -1;
        access(key);
        return valueMap.get(key);
    }

    public void put(int key, int value) {
        if (capa == 0) return;

        if (capa == valueMap.size() && !valueMap.containsKey(key)) { // !!! put 1,1 -> put 1,2
            LinkedHashSet<Integer> list = listMap.getOrDefault(least, new LinkedHashSet<>());
            if (list.size() > 0) {
                int removal = list.iterator().next();
                list.remove(removal);
                valueMap.remove(removal);
                countMap.remove(removal);
            }
        }

        least = 1;
        valueMap.put(key, value);
        access(key);
    }

    void access(int key) {
        // add
        int newCount = countMap.merge(key, +1, Integer::sum);
        LinkedHashSet<Integer> list = listMap.getOrDefault(newCount, new LinkedHashSet<>());
        list.add(key);
        listMap.put(newCount, list); // !!! needed, since newly allocated set is never added to map

        // remove
        list = listMap.get(newCount - 1);
        if (list != null && list.contains(key)) list.remove(key);

        if (listMap.get(least).size() == 0) least++; // !!! least is the minimum access count for O(1) access
        least = Math.min(least, newCount);          // !!!
    }
}

/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache obj = new LFUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */