172ms DoubleLinkedList nodes and HashMap O(1)


  • 0
    P

    The idea is based on this.
    We have double linked list for both node and frequency Node. Every frequency node has a double linkedlist node.

    For example, capacity, (1, 1) has frequency 1, (2, 2) and (3, 3) has frequency 3.

    FNode(-1) <-> FNode(1) <-> FNode(2) <-> FNode(-1) // FNode(-1) are dummy frequency nodes for head and tail.

    • list item ******* ↕ ************** ↕

    • list item Node(-1, -1) **** Node(-1, -1) //Node(-1,-1) are dummy nodes for head and tail.

    • list item ******* ↕ ***************** ↕

    • list item Node(1, 1)*******Node(2, 2)

    • list item ******* ↕ ***************** ↕

    • list item Node(-1. -1)*******Node(3, 3)

    • list item *************************** ↕

    • list item ********************* Node(-1, -1)

    public class LFUCache {
    class Node{
    int key, value, frequency;
    Node pre, next;
    Node(int key, int value, int frequency) {
    this.key = key;
    this.value = value;
    this.frequency = frequency;
    pre = null;
    next = null;
    }
    }
    class FNode{ // Frequency Node
    int frequency;
    Node node, last = null;
    FNode pre, next;
    FNode(int frequency,Node node) {
    this.frequency = frequency;
    this.node = node;
    pre = null;
    next = null;
    }
    }
    private int capacity;
    private Map<Integer, Node> nodeMap;
    private Map<Integer, FNode> frequencyMap;
    private FNode fHead = new FNode(-1, new Node(-1, -1, -1)); //we have a dummy head, to make it easy to delete node
    private FNode fTail = new FNode(-1, new Node(-1, -1, -1)); //we have a dummy tail, to make it easy to delete node
    public LFUCache(int capacity) {
    this.capacity = capacity;
    nodeMap = new HashMap<>();
    frequencyMap = new HashMap<>();
    fHead.next = fTail;
    fTail.pre = fHead;
    }

    public int get(int key) {
        if (capacity < 1 || !nodeMap.containsKey(key)) {
            return -1;
        }
        Node cur = nodeMap.get(key);
        int originalFrequency = cur.frequency;
        int frequency = originalFrequency + 1;
        update(key, originalFrequency, frequency);
        return cur.value;
    }
    
    public void set(int key, int value) {
        if (capacity < 1) {
            return;
        }
        int originalFrequency = 0;
        int frequency = 1;
        if (nodeMap.containsKey(key)) {
            nodeMap.get(key).value = value; //updated node value
            originalFrequency = nodeMap.get(key).frequency; // get the previous frequency
            frequency = originalFrequency + 1;//  previous frequency plus 1
            update(key, originalFrequency, frequency); //update node position in frequency node list
            return;
        } else if (nodeMap.size() == capacity) {
    		 FNode smallFrequencyNode = fHead.next; //since it is from small to large, the first one after head is the least frequency.
    		 Node tail = smallFrequencyNode.last;
    		 int dKey = tail.pre.key;
    		 deleteNode(tail.pre);//delete the least recently used node
    		 nodeMap.remove(dKey);//remove from node map
    		 	
    		 if (smallFrequencyNode.node.next == smallFrequencyNode.last) {// means there is no node in this frequency node, we need delete it
                deleteFNode(smallFrequencyNode);
                frequencyMap.remove(smallFrequencyNode.frequency);
    		 }
        }
        Node newNode = new Node(key, value, frequency);// otherwise it is a new node need to be added
        nodeMap.put(key, newNode);
        update(key, originalFrequency, frequency);
        
    
    }
    
    private void update(int key, int originalFrequency, int frequency) {
            nodeMap.get(key).frequency = frequency;// update frequency
            Node curNode = nodeMap.get(key);
            if (curNode.next != null) { //means if this node is already exist in frequencynode, we need move it out from that frequencynode
                deleteNode(curNode);
            }
            FNode FPresNode = frequencyMap.get(originalFrequency);
            if (!frequencyMap.containsKey(frequency)) { // we find this is a new frequency, so we need create a new node
                Node first = new Node(-1, -1, -1); //for each Node list, we also add dummy head and tail node
                Node last = new Node(-1, -1, -1);
                first.next = last;
                last.pre = first;
                moveToHead(curNode, first);// we move recently node to head.next
                
                FNode fNewNode = new FNode(frequency, first);
                fNewNode.last = last;// record last node in node list
                if(FPresNode == null) FPresNode = fHead;
                FPresNode.next.pre = fNewNode; //insert this new frequency node to frequency node list
                fNewNode.next = FPresNode.next;
                FPresNode.next = fNewNode;
                fNewNode.pre = FPresNode;
                frequencyMap.put(frequency, fNewNode);
                
            } else {
                FNode f = frequencyMap.get(frequency);
                moveToHead(curNode, f.node);
            }
            if (FPresNode != null && FPresNode != fHead && FPresNode.node.next == FPresNode.last) {// which means no node in this frequency, we need to remove this frequency node from frequency node list
                deleteFNode(FPresNode);
                frequencyMap.remove(originalFrequency);
            }
    }
    
    private void moveToHead(Node curNode, Node head) {// move the recently used node to head. since we have default head, so it actually move to head.next
    	curNode.next = head.next;
    	head.next.pre = curNode;
    	head.next = curNode;
    	curNode.pre = head;
    }    
    private void deleteNode(Node node) { //delete node
    	node.next.pre = node.pre; 
    	node.pre.next = node.next;
    	node.next = null;
    	node.pre = null;
    }
    private void deleteFNode(FNode node) { //delete frequency node
    	node.next.pre = node.pre;
    	node.pre.next = node.next;	    
    }	
    

    }


Log in to reply
 

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