1、前言

2、思路

这里我介绍一种比较蠢的解法，此解法虽然蠢，但是却和 LRU 是想通的，万一面试官真的让你实现 LFU 而不是 LRU，你也能立马想出来思路应对。此解法的时间复杂度为 O(n)。

不是说不想写 O(1) 的解法，而是 O(1) 的解法着实有点复杂，记着记着可能就忘记了。但是如果记住这种解法，等于记住了 LRU、LFU 两种写法，何乐而不为呢。

解法的总体思路：
总体上也是采用了一个 hashmap 加一个双向链表的实现，只不过此链表维护成从 head -> last 根据 frequency 单向递增的情况。

put 操作时，会将此节点放在 frequency 大于自己的 frequency 的节点后面，其他的思路基本跟 LRU 一致。

3、代码

class LFUCache {

    private Map<Integer, LFUListNode> map = new TreeMap<>();

    private Integer capacity;

    /**
     * 链表根据 frequency 从小大大排列
     */
    private LFUListNode head, last;

    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.head = new LFUListNode(null, null, -1, -1, Integer.MIN_VALUE);
        this.last = new LFUListNode(null, null, -1, -1, Integer.MAX_VALUE);
        this.head.next = this.last;
        this.last.pre = this.head;
    }
    
    public int get(int key) {
        LFUListNode node = map.get(key);
        if(node == null){
            return -1;
        }
        node.frequency++;
        // 移除此节点
        removeNode(node);
        // 移到 frequency 大于此节点的后面
        movePosition(node);
        return node.value;
    }
    
    public void put(int key, int value) {
        if(capacity == 0){
            return;
        }
        LFUListNode node = map.get(key);
        if(node != null){
            node.value = value;
            node.frequency++;
            // 移除此节点
            removeNode(node);
            // 移到 frequency 大于此节点的后面
            movePosition(node);
            return;
        }

        // 满了则移除末尾节点
        if(this.map.size() + 1 > this.capacity){
            node = removeHead();
            this.map.remove(node.key);
        }
        node = new LFUListNode(null, null, key, value, 1);
        this.map.put(key, node);
        // 移到 frequency 大于此节点的后面
        movePosition(node);
    }

    /**
     * 将此节点链接到 frequency 大于此节点的后面
     * @param node
     */
    private void movePosition(LFUListNode node) {
        LFUListNode first = this.head;
        while (node.frequency >= first.frequency){
            first = first.next;
        }

        LFUListNode pre = first.pre;
        node.next = first;
        node.pre = pre;
        pre.next = node;
        first.pre = node;
    }


    /**
     * 移除节点
     * @param node
     */
    private void removeNode(LFUListNode node) {
        LFUListNode pre = node.pre;
        LFUListNode next = node.next;
        pre.next = next;
        next.pre = pre;
        node.pre = null;
        node.next = null;
    }

    /**
     * 移除头节点
     * @return
     */
    private LFUListNode removeHead() {
        LFUListNode nextNode = this.head.next;
        nextNode.next.pre = this.head;
        nextNode.pre.next = nextNode.next;
        nextNode.pre = null;
        nextNode.next = null;

        return nextNode;
    }

    class LFUListNode {
        LFUListNode next;
        LFUListNode pre;
        Integer key;
        Integer value;
        Integer frequency;

        public LFUListNode() {
        }

        public LFUListNode(LFUListNode next, LFUListNode pre, Integer key, Integer value, Integer frequency) {
            this.next = next;
            this.pre = pre;
            this.key = key;
            this.value = value;
            this.frequency = frequency;
        }
    }

    public static void main(String[] args) {
        LFUCache lFUCache = new LFUCache(2);
        lFUCache.put(1, 1);   // cache=[1,_], cnt(1)=1
        lFUCache.put(2, 2);   // cache=[2,1], cnt(2)=1, cnt(1)=1
        System.out.println(lFUCache.get(1));      // 返回 1
                              // cache=[1,2], cnt(2)=1, cnt(1)=2
        lFUCache.put(3, 3);   // 去除键 2 ，因为 cnt(2)=1 ，使用计数最小
                              // cache=[3,1], cnt(3)=1, cnt(1)=2
        System.out.println(lFUCache.get(2));      // 返回 -1（未找到）
        System.out.println(lFUCache.get(3));      // 返回 3
                              // cache=[3,1], cnt(3)=2, cnt(1)=2
        lFUCache.put(4, 4);   // 去除键 1 ，1 和 3 的 cnt 相同，但 1 最久未使用
                              // cache=[4,3], cnt(4)=1, cnt(3)=2
        System.out.println(lFUCache.get(1));      // 返回 -1（未找到）
        System.out.println(lFUCache.get(3));      // 返回 3
                              // cache=[3,4], cnt(4)=1, cnt(3)=3
        System.out.println(lFUCache.get(4));      // 返回 4
                             // cache=[3,4], cnt(4)=2, cnt(3)=3
    }
}