🌕🌗 460. LFU 缓存

难度: 🌕🌗

问题描述

---

解法

class LFUCache {
    int size; // 节点数
    int capacity; // 容量
    HashMap<Integer, Node> map; // 根据 key 快速定位到节点
    // 根据 fre 快速定位到当前 fre 下的链表，借助 LinkedList 快速删除首尾节点
    // 实际上，当 LinkedList 节点数过多时，要删除其中某个元素，复杂度不止 1
    // 插入节点放入尾部，移除节点从头结点开始
    HashMap<Integer, LinkedList<Node>> freMap; 
    int minFre; // 记录最小 fre 便于快速定位到该 fre 下的链表

    public LFUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        this.map = new HashMap<>();
        this.freMap = new HashMap<>();
        this.minFre = 0;
    }
    
    public int get(int key) {
        if(capacity == 0 || !map.containsKey(key)) {
            return -1;
        }
        Node select = map.get(key);
        // get() 调用一次，fre ++，移到新的对应频次的列表中
        int oldFre = select.fre;
        LinkedList<Node> oldList = freMap.get(oldFre);
        oldList.remove(select); // 从旧链表中删除该节点
        freMap.put(oldFre, oldList); // 更新 freMap
        // 更新 minFre
        if(oldList.size() == 0 && minFre == oldFre) {
            minFre = oldFre + 1;
        }        
        int newFre = oldFre + 1;
        select.fre = newFre;
        // 判断新频次下的链表是否存在
        if(!freMap.containsKey(newFre)) {
            LinkedList<Node> tmpList = new LinkedList<>();
            freMap.put(newFre, tmpList);
        }
        LinkedList<Node> newList = freMap.get(newFre);
        newList.addLast(select);
        freMap.put(newFre, newList);
        return select.val;
    }
    
    public void put(int key, int value) {
        // System.out.println(key + "  " + minFre);
        if(capacity == 0) {
            return;
        }
        if(map.containsKey(key)) {
            Node select = map.get(key);
            select.val = value;
            get(key);
        } else {
            // 判断容量是否足够
            if(size == capacity) {
                // 需要先移除最小频次下的首个节点
                LinkedList<Node> oldestList = freMap.get(minFre);
                Node rv = oldestList.get(0);
                oldestList.removeFirst();
                size --;
                map.remove(rv.key);
            }
            // 更新 minFre - 既然新插入了一个节点，那么 minFre 必 == 1
            minFre = 1;
            Node insert = new Node(key, value);
            if(!freMap.containsKey(1)) {
                LinkedList<Node> tmpList = new LinkedList<>();
                freMap.put(1, tmpList);
            }
            LinkedList<Node> insertList = freMap.get(1);
            insertList.addLast(insert);
            size ++;
            map.put(key, insert);
            freMap.put(1, insertList);
        }
    }
}

// 构造双向链表节点类
class Node {
    int key;
    int val;
    int fre;
    Node next;
    Node prev;
    public Node(int key, int val) {
        this.key = key;
        this.val = val;
        this.fre = 1;
    }
}

/**
 * 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);
 */

---

输出