题解 | #设计LFU缓存结构#

import java.util.*;

public class Solution {
    public int[] LFU(int[][] operators, int k) {//批量操作
        LFUCache lfucache = new LFUCache(k);
        List<Integer> list = new ArrayList<>();
        for (int[] operator : operators) {
            if (operator[0] == 1) {//1-新增
                lfucache.set(operator[1], operator[2]);
            } else if (operator[0] == 2) {//2-获取
                int value = lfucache.get(operator[1]);
                list.add(value);
            }
        }
        int[] res = new int[list.size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = list.get(i);
        }
        return res;
    }
}

//LFU缓存设置
class LFUCache {
    class Node {
        int key;
        int value;
        int freq;//频率

        public Node(int key, int value, int freq) {
            this.key = key;
            this.value = value;
            this.freq = freq;
        }
    }

    private int capacity;
    private int size;
    private int minFreq;//频率最低
    private HashMap<Integer, Node> cache;//缓存
    private HashMap<Integer, LinkedHashSet<Node>>
    freqList;//缓存频率表(每个频次都有一个表），因为有很多相同频次的数据

    public LFUCache(int capacity) {
        this.capacity = capacity;
        size = 0;
        minFreq = 0;
        cache = new HashMap<>();
        freqList = new HashMap<>();
    }

    public int get(int key) {//获取
        if (!cache.containsKey(key)) {
            return -1;
        }
        Node node = cache.get(key);
        updateNode(node);
        return node.value;
    }

    public void set(int key, int value) {
        if (capacity == 0) {
            return;
        }
        //存在则更新
        if (cache.containsKey(key)) {
            Node node = cache.get(key);
            node.value = value;
            updateNode(node);
        } else {//不存在则新增
            if (size == capacity) {//空间占满，删除频率最低数据
                LinkedHashSet<Node> minFreqList = freqList.get(
                                                      minFreq);//获取最小频率列表
                Node node = minFreqList.iterator().next();//获取第一个节点
                minFreqList.remove(node);//移除节点
                cache.remove(node.key);//缓存也移除
                size--;
            }
            //新增节点-加入缓存-加入频率表-更新最小频次和缓存大小
            Node newNode = new Node(key, value, 1);
            cache.put(key, newNode);
            LinkedHashSet<Node> newList = freqList.getOrDefault(1, new LinkedHashSet<>());
            newList.add(newNode);
            freqList.put(1, newList);
            minFreq = 1;
            size++;
        }
    }

    private void updateNode(Node node) {//更新数据频率
        //取出-移除
        LinkedHashSet<Node> oldList = freqList.get(node.freq);//获取该频次的列表
        oldList.remove(node);//移除该节点
        if (oldList.isEmpty() &&
                node.freq == minFreq) {//如果这数据是该表最后一个数据并且是最低频率
            //更新最小频率
            minFreq++;
        }
        //更新-新增
        node.freq++;
        //获取该频次的列表(没有则新增)
        LinkedHashSet<Node> newList = freqList.getOrDefault(node.freq,
                                      new LinkedHashSet<>());
        newList.add(node);//列表新增节点
        freqList.put(node.freq,
                     newList);//放入(列表存在则更新,不存在则新增)
    }
}