Java O(n) Solution using one HashMap one Doubly Linked List


  • 0
    J
    public class LFUCache {
        class DLNode {
            int key,val,freq;
            DLNode pre,next;
            DLNode(int key,int value) {
                this.key = key;
                this.val = value;
                this.freq = 1;
            }
        }
        class DLList {
            DLNode head,tail;
            DLList() {
                head = new DLNode(0,0);
                tail = new DLNode(0,0);
                head.next = tail;
                tail.pre = head;
            }
            
            public DLNode removeTheTail() {
                DLNode node = tail.pre;
                node.pre.next = tail;
                tail.pre = node.pre;
                return node;
            }
            
            public void remove(DLNode node) {
                node.pre.next = node.next;
                node.next.pre = node.pre;
            }
            
            public void moveForward(DLNode node) {
                DLNode cur = tail, next=cur;
                while(cur!=head&&node.freq>=cur.freq) {
                    next = cur;
                    cur = cur.pre;
                }
                next.pre = node;
                node.next = next;
                node.pre = cur;
                cur.next = node;
            }
        }
        int cap;
        Map<Integer,DLNode> map;
        DLList list;
    
        public LFUCache(int capacity) {
            this.cap = capacity;
            this.map = new HashMap<Integer,DLNode>();
            this.list = new DLList();
        }
        
        public int get(int key) {
            if(!map.containsKey(key))
                return -1;
            DLNode node = map.get(key);
            node.freq++;
            list.remove(node);
            list.moveForward(node);
            return node.val;
        }
        
        public void put(int key, int value) {
            if(cap==0)
                return;
            if(map.containsKey(key)) {
                DLNode node = map.get(key);
                node.val = value;
                node.freq++;
                list.remove(node);
                list.moveForward(node);
                return;
            }
            if(map.size()==cap) {
                DLNode node = list.removeTheTail();
                map.remove(node.key);
            }
            DLNode n = new DLNode(key,value);
            list.moveForward(n);
            map.put(key,n);
        }
    }
    

Log in to reply
 

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