O(1) with single HashMap and linked lists.


  • 0
    H
    public class LFUCache {
        int capacity, count;
        Map<Integer, Node> nodes;
        Bucket head, tail;
        
    
        public LFUCache(int capacity) {
            this.capacity = capacity;    
            this.count = 0;
            this.head = createBucket(0);
            this.tail = createBucket(0);
            head.next = tail;
            tail.prev = head;
            nodes = new HashMap<Integer, Node>();
        }
        
        Bucket createBucket(int hc) {
            Bucket b = new Bucket();
            Node head = new Node();
            Node tail = new Node();
            head.next = tail;
            tail.prev = head;
            b.hitcount = hc;
            b.head = head;
            b.tail = tail;
            
            return b;
        }
        
        public int get(int key) {
            if (!nodes.containsKey(key)) return -1;
            
            Node node = nodes.get(key);
            incrHit(node);
            
            return node.value;
        }
        
        public void set(int key, int value) {
            if (capacity == 0) return;
            
            Node node = null;
            if (!nodes.containsKey(key)) {
                count++;
                if (count > capacity) {
                    Bucket b = head.next;
                    Node last = b.tail.prev;
                    // System.out.format("hc: %d, last = <%d,%d>\n", b.hitcount, last.key, last.value);
                    last.prev.next = last.next;
                    last.next.prev = last.prev;
                    nodes.remove(last.key);
                    count--;
                    if (b.head.next == b.tail) {
                        b.next.prev = b.prev;
                        b.prev.next = b.next;
                    }
                }
                
                node = new Node();
                node.key = key;
                node.bucket = head;
                nodes.put(key, node);
            } else node = nodes.get(key);
            
            node.value = value;
            incrHit(node);
        }
        
        void incrHit(Node node) {
            Bucket b = node.bucket;
            if (b != head) {
                node.next.prev = node.prev;
                node.prev.next = node.next;
            }
            
            Bucket nb = null;
            if (b.next.hitcount == (b.hitcount + 1)) {
                nb = b.next;
            } else {
                nb = createBucket(b.hitcount + 1);
                b.next.prev = nb;
                nb.next = b.next;
                b.next = nb;
                nb.prev = b;
            }
            
            if (b != head && b.head.next == b.tail) {
                b.next.prev = b.prev;
                b.prev.next = b.next;
            }
            
            nb.head.next.prev = node;
            node.next = nb.head.next;
            nb.head.next = node;
            node.prev = nb.head;
            node.bucket = nb;
        }
        
        class Node {
            int value, key;
            Node prev, next;
            Bucket bucket;
        }
        
        class Bucket {
            int hitcount;
            Node head, tail;
            Bucket prev, next;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.