LeetCode.460.LFU Cache 实现LFU缓存

题目描述

460 LFU Cache
https://leetcode-cn.com/problems/lfu-cache/

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.

Note that the number of times an item is used is the number of calls to the get and put functions for that item since it was inserted. This number is set to zero when the item is removed.

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 1
cache.put(3, 3);    // evicts key 2
cache.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 3
cache.get(4);       // returns 4

---

解题过程

这道题是自从参加 2020 年 LeetCode 中国区的 三四月 每日一题 以来最难的一道题，难度不止体现在怎么实现 O(1) 算法，即便只是求其次实现 O(logn) 算法，写起来也很费劲。

这道题得对于 java 的集合类非常熟练才行。

HashMap+TreeSet实现O(logn)方法

使用 HashMap 和 TreeSet 的算法我也是看了题解才会写，而且调了好长时间。
get 时，TreeSet 中需要删除和重新插入，时间复杂度是 O(logn)
put 时，TreeSet 的插入也是 O(logn)

private static class LFUCache {
    // LFUCache 的固定容量
    private int capacity;
    // 全局的计数器，代表时间，用于对访问次数相同的key再按时间排序
    private int time;
    // 按 (LFUNode.frequent 升序, LFUNode.time 升序) 排序的有序集合，红黑树实现， get 和 add 是 O(logn) 复杂度
    private TreeSet<LFUNode> frequentSet;
    // 存储数据的 map
    private Map<Integer, LFUNode> dataMap;

    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.time = 1;
        // 如果 自定义类 LFUNode 没有实现 Comparable 接口的 compareTo 方法，就必须在创建 TreeSet 时指定排序方法
        frequentSet = new TreeSet<>((k1, k2) -> k1.frequent == k2.frequent ? k1.time - k2.time : k1.frequent - k2.frequent);
        dataMap = new HashMap<>();
    }

    public int get(int key) {
        LFUNode existedNode = dataMap.get(key);
        if (null == existedNode) {
            return -1;
        }
        frequentSet.remove(existedNode);
        existedNode.frequent++; // 访问次数加1
        existedNode.time = time++; // 更新全局时间
        frequentSet.add(existedNode);
        System.out.println("after get: " + frequentSet);
        return existedNode.value;
    }

    public void put(int key, int value) {
        // 测试用例中有 capacity 为0的特例
        if (capacity == 0) {
            return;
        }
        LFUNode existedNode = dataMap.get(key);
        if (existedNode != null) {
            // 注意一定要先删除
            frequentSet.remove(existedNode);
            // 已存在key，更新value
            existedNode.value = value; // 更新value
            existedNode.frequent++; // 访问次数加1
            existedNode.time = time++; // 更新全局时间
            dataMap.put(key, existedNode);
            frequentSet.add(existedNode);
        } else {
            // 新key，先看空间够不够
            if (dataMap.size() == capacity) {
                // 空间不够时删除访问次数最小的，若有多个删除time最小的，也就是有序集合 TreeSet 的第一个元素
                LFUNode lfuNode = frequentSet.first();
                frequentSet.remove(lfuNode);
                dataMap.remove(lfuNode.key);
                System.out.println("after remove lfu in put: " + frequentSet);
            }
            LFUNode newNode = new LFUNode(key, value, 1, time++);
            dataMap.put(key, newNode);
            frequentSet.add(newNode);
        }
        System.out.println("after put: " + frequentSet);
    }

    // LFUCache 的结点
    class LFUNode {
        int key;
        int value;
        int frequent;
        int time;

        LFUNode(int key, int value, int frequent, int time) {
            this.key = key;
            this.value = value;
            this.frequent = frequent;
            this.time = time;
        }

        @Override
        public String toString() {
            return "{" + key + "=" + value + ", f:" + frequent + ", t:" + time + "}";
        }
    }
}

HashMap+双向链表实现O(1)方法

用结点 Node 封装 key, value, frequent
用一个 HashMap dataMap 存储数据 key -> Node
用一个 HashMap frequentMap 存储访问次数和这个访问次数的结点集合 frequent -> LinkedHashSet<Node>
get 时，从 dataMap 获取 Node，从 frequentMap 获取这个 Node 的访问次数集合，从中O(1)删除当前 Node，次数加1，O(1)插入新频次的集合中，由于 LinkedHashSet 按插入顺序排序，插入后是在当前频次的集合末尾。
put 时，如果当前key存在，和get处理流程一样，多了个更新value。如果当前key不存在，先判断容量是否满了，若满了找到频次最小的那个 LinkedHashSet （所以要维护一个全局变量 min 存储当前的最小频次），O(1) 删除这个set的第一个元素，也就是同频次的最长时间没访问的。然后构造新Node插入 dataMap，同时插入频次为 1 的 frequentMap 的 set

---

GitHub代码

algorithms/leetcode/leetcode/_460_LFUCache.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_460_LFUCache.java

---