Java O(1), two hashMap, and one double linked list (147ms)


  • 0
    S

    Two Maps:
    vals : key is the input key, value is the self-defined ListNode for double-linkedList
    freqs : key is the freq number, value the self-defined FreqNode class representing the head and tail ListNode with this specific frequent.

    global minFreq : to recode the current minimul frequency. In order to remove the oldest ListNode with least frequency in O(1) when it reaches the capacity

    Example :
    vals : L1(key, value, freq)
    1 : L1(1,1,1)
    2 : L2(2,2,3)
    3 : L3(3,3,3)
    4 : L4(4,4,1)
    5 : L5(3,3,3)

    freqs:
    1 : L1 -> L4
    head tail
    3: L2 -> L3 -> L5
    head tail

    if we want to put(3,3)
    The expected status of vals and maps would be :
    vals : L1(key, value, freq)
    1 : L1(1,1,1)
    2 : L2(2,2,3)
    3 : L3(3,3,4)
    4 : L4(4,4,1)
    5 : L5(3,3,3)

    freqs:
    1 : L1 -> L4
    head tail
    3: L2 -> L5
    head tail
    4 : L3
    head/tail

    "remove" function is to remove L3 from freqs.get(3)
    Two tricky part :
    (1)when the ListNode you want to remove is from the minFreq and there is only one ListNode under this frequence --> your minFreq should increase by 1
    (2) when the ListNode you want to remove is the only one under certain frequency --> you need to remove the entry with this frequnecy in freqs Map

    "Insert" function : is to insert L3 to a new entry with old frequency + 1

    class LFUCache {
        private Map<Integer, ListNode> vals; //<key, ListNode>
        private Map<Integer, FreqNode> freqs; //<freq, freqNode>
        private final int capacity;
        private int minFreq = -1;
        
        public LFUCache(int capacity) {
            this.capacity = capacity;
            vals = new HashMap<>();
            freqs = new HashMap<>();
        }
        
        public int get(int key) {
            //System.out.println("get " + key);
            ListNode curNode = vals.get(key);
            if (curNode == null) {
                return -1;
            }
            
            FreqNode freqNode = freqs.get(curNode.freq);
            remove(curNode, freqNode);
    
            FreqNode nextFreqNode = freqs.get(curNode.freq + 1);
            insert(curNode, nextFreqNode);
            return curNode.val;
            
        }
        
        public void put(int key, int value) {
            //System.out.println("put " + key + " " + value);
            if (capacity <= 0) {
                return;
            }
            
            ListNode curNode = vals.get(key);
            if (curNode != null) {
                FreqNode freqNode = freqs.get(curNode.freq);
                
                remove(curNode, freqNode);
                
                FreqNode nextFreqNode = freqs.get(curNode.freq + 1);
                insert(curNode, nextFreqNode);
                curNode.val = value;
                return;
            }
            
            if (vals.size() == capacity) {
                //remove the tail in the least frequent 
                
                FreqNode minFreqNode = freqs.get(minFreq);
                ListNode tail = minFreqNode.tail;
                remove(minFreqNode.tail, minFreqNode);
                vals.remove(tail.key);
            }
            
            minFreq = 1;
            curNode = new ListNode(key, value, 0);
            FreqNode nextFreqNode = freqs.get(1);
            insert(curNode, nextFreqNode);
            vals.put(key, curNode);
    
        }
        
        private void remove(ListNode curNode, FreqNode freqNode) {
                if (curNode.prev != null) {
                    curNode.prev.next = curNode.next;
                }
                if (curNode.next != null) {
                    curNode.next.prev = curNode.prev;
                }
                if (freqNode.head == curNode) {
                    freqNode.head = curNode.next;
                }
                if (freqNode.tail == curNode) {
                    freqNode.tail = curNode.prev;
                }
              
                curNode.prev = null;
                curNode.next = null;
    //minFreq should plus one, when you remove  the only ListNode in minimul frequency
                if (curNode.freq == minFreq && freqNode.head == null) {
                    minFreq++;
                }    
    //remove the entry in freqs Map when you remove the only freqNode in this frequency
                if (freqNode.head == null) {
                	freqs.remove(curNode.freq);
                }
               
        }
        
        private void insert(ListNode curNode, FreqNode nextFreqNode) {
            if (nextFreqNode == null) {
                nextFreqNode = new FreqNode();
                nextFreqNode.head = curNode;
                nextFreqNode.tail = curNode;
                freqs.put(curNode.freq + 1, nextFreqNode);
            } else {
                    //insertHead
                curNode.next = nextFreqNode.head;
                nextFreqNode.head.prev = curNode;
                nextFreqNode.head = curNode;
            }
         
            curNode.freq = curNode.freq + 1;
        }
        
    }
    
    class ListNode {
        int key;
        int val;
        int freq;
        ListNode prev;
        ListNode next;
        public ListNode(int key, int val, int freq) {
            this.key = key;
            this.val = val;
            this.freq = freq;
        } 
    }
    
    //The ListNode of the head and tail to make remove in operation O(1) when reach capacity
    class FreqNode {
        ListNode head;
        ListNode tail;
        public FreqNode() {
        }
    }
    

Log in to reply
 

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