Java O(1) AC Using 2 HashMap


  • 0
    K
    public class LFUCache {
        private class Node{
            private int key, value, freq;
            public Node(int k, int v){
                key = k;
                value = v;
            }
        }
        
        private HashMap<Integer, Node> map;
        private HashMap<Integer, LinkedList<Node>> freqMap;
        private int lf, capacity;
        
        public LFUCache(int capacity) {
            map = new HashMap<Integer, Node>(capacity);
            freqMap = new HashMap<Integer, LinkedList<Node>>();
            this.capacity = capacity;
        }
        
        private void updateLF(int newFreq){
            if(newFreq < lf)
                lf = newFreq;
            else if(lf == newFreq - 1 && freqMap.get(lf) == null)
                lf++;
        }
        
        private void moveNode(Node n){
            if(n.freq > 0){
                freqMap.get(n.freq).remove(n);
                if(freqMap.get(n.freq).size() == 0)
                    freqMap.remove(n.freq);
            }
                
            n.freq++;
            
            if(freqMap.get(n.freq) == null)
                freqMap.put(n.freq, new LinkedList<Node>());
                
            freqMap.get(n.freq).addFirst(n);
            
            updateLF(n.freq);
        }
        
        public int get(int key) {
            Node n = map.get(key);
            if(n == null) return -1;
            moveNode(n);
            
            return n.value;
        }
        
        private void removeLFUsed(){
            Node n = freqMap.get(lf).getLast();
            map.remove(n.key);
            freqMap.get(lf).remove(n);
        }
        
        public void put(int key, int value) {
            if(capacity > 0){
                Node n = map.get(key);
                if(n == null){
                    if(map.size() == capacity)
                        removeLFUsed();
                    
                    n = new Node(key, value);
                    map.put(key, n);
                }
                else n.value = value;
                
                moveNode(n);
            }
        }
    }
    

Log in to reply
 

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