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

时间复杂度GET和SET都是O(1)，空间复杂度O(n),就是有点蛋疼，懒得优化了

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * lfu design
     * @param operators int整型二维数组 ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public int[] LFU (int[][] operators, int k) {
        if (k == 0) {
            return new int[0];
        }
        capacity = k;
        List<Integer> retList = new ArrayList<>();
        for (int[] operator : operators) {
            if (operator[0] == 1) {
                set(operator[1], operator[2]);
            } else {
                retList.add(get(operator[1]));
            }
        }
        int[] res = new int[retList.size()];
        for (int i = 0; i < retList.size(); i++) {
            res[i] = retList.get(i);
        }
        return res;
    }

    private static class Node {
        private final int key;
        private Node left, right, up, down;

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

    private static class KeyValOpTime {
        private int key;
        private int val;
        private int opTime;

        public KeyValOpTime(int key, int val, int opTime) {
            this.key = key;
            this.val = val;
            this.opTime = opTime;
        }
    }

    private static final Map<Integer, KeyValOpTime> keyMap = new HashMap<>();
    private static final Map<Integer, Node> opMap = new HashMap<>();
    private static final Map<Integer, Node> keyNodeMap = new HashMap<>();

    private int capacity;
    private Node opRoot;
    private int sz;

    private void deleteLowerestQuery() {
        if (opRoot.up == opRoot) {
            while (opRoot.up == opRoot) {
                opRoot = opRoot.right;
            }
        }
        Node opNode = opRoot;
        Node tmp = opNode.up;
        keyMap.remove(tmp.key);
        keyNodeMap.remove(tmp.key);
        Node node = opNode.up.up;
        opNode.up = node;
        node.down = opNode;
        if (opNode.up == opNode) {
            node = opNode.right;
            opNode.right = null;
            if (node != null) {
                node.left = null;
            }
            opRoot = node;
        }
        sz--;
    }

    private void set(int key, int value) {
        int opTime;
        if (!keyMap.containsKey(key)) {
            if (sz == capacity) {
                deleteLowerestQuery();
            }
            opTime = 1;
            keyMap.put(key, new KeyValOpTime(key, value, opTime));
            if (opRoot == null) {
                opRoot = new Node(opTime);
                Node node = new Node(key);
                opRoot.down = node;
                node.up = opRoot;
                opRoot.up = node;
                node.down = opRoot;
                opMap.put(opTime, opRoot);
                keyNodeMap.put(key, node);
                sz++;
            } else if (!opMap.containsKey(opTime)) {
                Node opNode = new Node(opTime);
                Node node = new Node(key);
                opNode.down = node;
                node.up = opNode;
                opNode.up = node;
                node.down = opNode;
                opNode.right = opRoot;
                opRoot.left = opNode;
                opMap.put(opTime, opNode);
                keyNodeMap.put(key, node);
                opRoot = opRoot.left;
                sz++;
            } else {
                Node opNode = opMap.get(opTime);
                Node node = new Node(key);
                Node down = opNode.down;
                node.down = down;
                down.up = node;
                node.up = opNode;
                opNode.down = node;
                keyNodeMap.put(key, node);
                sz++;
            }
        } else {
            KeyValOpTime keyValOpTime = keyMap.get(key);
            opTime = keyValOpTime.opTime;
            keyValOpTime.val = value;
            keyValOpTime.opTime = opTime + 1;
            keyMap.put(key, keyValOpTime);
            dealWithMap(key, opTime);
        }
    }

    private void dealWithMap(int key, int opTime) {
        Node opNode = opMap.get(opTime);
        Node node = keyNodeMap.get(key);
        Node tmp = node.down;
        node.up.down = tmp;
        tmp.up = node.up;
        if (opMap.get(opTime + 1) == null) {
            tmp = new Node(opTime + 1);
            tmp.down = node;
            node.up = tmp;
            tmp.up = node;
            node.down = tmp;
            Node right = opNode.right;
            tmp.right = right;
            if (right != null) {
                right.left = tmp;
            }
            opNode.right = tmp;
            tmp.left = opNode;
            opMap.put(opTime + 1, tmp);
        } else {
            Node right = opMap.get(opTime + 1);
            tmp = right.down;
            node.down = tmp;
            tmp.up = node;
            right.down = node;
            node.up = right;
        }
        if (opNode.down == opNode) {
            Node left = opNode.left;
            Node right = opNode.right;
            right.left = left;
            if (left != null) {
                left.right = right;
            }
            opMap.remove(opTime);
        }
    }

    private int get(int key) {
        if (!keyMap.containsKey(key)) {
            return -1;
        }
        KeyValOpTime keyValOpTime = keyMap.get(key);
        int value = keyValOpTime.val;
        int opTime = keyValOpTime.opTime;
        keyValOpTime.opTime = opTime + 1;
        keyMap.put(key, keyValOpTime);
        dealWithMap(key, opTime);
        return value;
    }
}