460. LFU Cache

 一刷 08/2022

Version #1 Map of DoublyLinkedList

Time O(1) for all

Space O(N) - N is number of keys

Runtime: 67 ms, faster than 95.05% of Java online submissions for LFU Cache.

Memory Usage: 134.1 MB, less than 77.48% of Java online submissions for LFU Cache.

class LFUCache {

    // key-the counter, value-the most recent used node with this counter

    Map<Integer, DList> counterToList;

    Map<Integer, Node> keyToNode;

    int cap;

    int minCounter;

    class Node {

        Node prev, next;

        int key;

        int val;

        int counter;

        public Node(int key, int val) {

            this.key = key;

            this.val = val;

            this.counter = 1;

        }

    }

    

    class DList {

        Node head, tail;

        int size;

        public DList() {

            this.head = new Node(0, 0);

            this.tail = new Node(0, 0);

            head.next = tail;

            tail.prev = head;

            this.size = 0;

        }

        

        // add after head

        public void add(Node node) {

            Node next = head.next;

            head.next = node;

            node.next = next;

            node.prev = head;

            next.prev = node;

            size++;

        }

        

        public void remove(Node node) {

            Node prev = node.prev;

            Node next = node.next;

            prev.next = next;

            next.prev = prev;

            size--;

        }

        

        // remove the last element and returns its key

        public int removeLast() {

            if (size == 0) {

                return 0;

            }

            size--;

            Node last = tail.prev;

            Node prev = last.prev;

            prev.next = tail;

            tail.prev = prev;

            return last.key;

        }

    }

    

    public LFUCache(int capacity) {

        this.cap = capacity;

        this.minCounter = 0;

        counterToList = new HashMap<>();

        keyToNode = new HashMap<>();

    }

    

    public int get(int key) {

        if (!keyToNode.containsKey(key)) {

            return -1;

        }

        Node curr = keyToNode.get(key);

        DList list = counterToList.get(curr.counter);

        list.remove(curr);

        if (list.size == 0 && curr.counter == minCounter) {

            minCounter++;

        }

        

        curr.counter++;

        counterToList.putIfAbsent(curr.counter, new DList());

        counterToList.get(curr.counter).add(curr);

        return curr.val;

    }

    

    public void put(int key, int value) {

        if (keyToNode.containsKey(key)) {

            keyToNode.get(key).val = value;

            get(key);

            return;

        }

        if (cap == 0) {

            if (minCounter == 0) {

                return;

            }

            cap++;

            DList list = counterToList.get(minCounter);

            int removedKey = list.removeLast();

            keyToNode.remove(removedKey);

        }

        minCounter = 1;

        cap--;

        Node curr = new Node(key, value);

        counterToList.putIfAbsent(1, new DList());

        counterToList.get(1).add(curr);

        keyToNode.put(key, curr);

    }

}