O(1) Solution without using LinkedHashMap


  • 0

    The basic Idea is that use a HashMap leader to record the most recent record in the same frequency and design logic to maintain the leader.

    '''

    class LFUCache {

    int capacity;
    Map<Integer,DLinkedNode> mapping;
    Map<Integer,DLinkedNode> leader;
    DLinkedNode head;
    DLinkedNode tail;
    
    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.mapping = new HashMap<>();
        this.leader = new HashMap<>();
        this.head = new DLinkedNode(0,0);
        this.tail = new DLinkedNode(0,0);
        this.head.right = this.tail;
        this.tail.left = this.head;
    }
    
    public int get(int key) {
        if(this.capacity == 0) return -1;
        if(mapping.containsKey(key)){
            update(key);
            return mapping.get(key).value;
        }
        else{
            return -1;
        }
    }
    
    public void put(int key, int value) {
        if(this.capacity == 0) return;
        if(mapping.size() == capacity && !mapping.containsKey(key)){
            DLinkedNode temp = this.head.right;
            if(leader.containsKey(temp.count) && leader.get(temp.count) == temp)
                leader.remove(temp.count);
            mapping.remove(temp.key);
            delete(temp);
        }
        if(mapping.containsKey(key)){
            update(key);
            mapping.get(key).value = value;
        }
        else{
            DLinkedNode newD = new DLinkedNode(key,value);
            newD.count = 0;
            mapping.put(key,newD);
            if(leader.containsKey(0)){
                insertAfterTarget(newD,leader.get(0));
                leader.put(0,newD);
            }
            else{
                leader.put(0,newD);
                insertAfterTarget(newD,this.head);
            }
        }
    }
    
    
    class DLinkedNode{
        int key;
        int value;
        int count;
        DLinkedNode left;
        DLinkedNode right;
    
        public DLinkedNode(int key, int value){
            this.key = key;
            this.value = value;
            this.count = 0;
            this.left = null;
            this.right = null;
        }
    }
    
    public void delete(DLinkedNode d){
        d.left.right = d.right;
        d.right.left = d.left;
    }
    
    public void insertAfterTarget(DLinkedNode d, DLinkedNode target){
        d.left = target;
        d.right = target.right;
        target.right = d;
        d.right.left = d;
    }
    
    public void insertBeforeTarget(DLinkedNode d, DLinkedNode target){
        d.right = target;
        d.left = target.left;
        target.left = d;
        d.left.right = d;
    }
    
    
    public void update(int key){
        boolean flag = false;
        DLinkedNode temp = mapping.get(key);
        if(leader.get(temp.count) == temp){
            flag = true;
            if(temp.left != this.head && temp.left.count == temp.count){
                leader.put(temp.count,temp.left);
            }
            else{
                leader.remove(temp.count);
            }
        }
        // else{
        //     delete(temp);
        //     insertAfterTarget(temp,leader.get(temp.count));
        // }
        temp.count+=1;
        if(leader.containsKey(temp.count)){
            delete(temp);
            insertAfterTarget(temp,leader.get(temp.count));
        }
        else{
            if(!flag){
                delete(temp);
                insertAfterTarget(temp,leader.get(temp.count-1));
            }
        }
        leader.put(temp.count,temp);
    }
    

    }
    '''


Log in to reply
 

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