HashMap n TreeSet Solution


  • 0
    C
    public class LFUCache {
        int capacity;
        Map<Integer, Node> map = new HashMap<>();
        
        TreeSet<Node> tree = new TreeSet<>(new Comparator<Node>(){
            public int compare(Node a , Node b){
                if(a.key == b.key){
                    return 0;
                }
                int s = (a.count - b.count);
                if(s!=0) return s;
                else return a.timestamp-b.timestamp > 0 ? 1 :-1;
            }
        });
    
        public LFUCache(int capacity) {
            this.capacity = capacity;
        }
        
        public int get(int key) {
            if(!map.containsKey(key)){
                return -1;
            }
            
            Node n = map.get(key);
            tree.remove(n);
            n.increment();
           
            tree.add(n);
            return map.get(key).value;
        }
        
        public void set(int key, int value) {
            if(capacity == 0){
                return;
            }
            if(map.size() == capacity && !map.containsKey(key)){
                Node n = tree.pollFirst();
                map.remove(n.key);
            }
            
            
            if(map.containsKey(key)){
               Node n = map.get(key);
               n.value = value;
               tree.remove(n);
               n.increment();
               tree.add(n);
               
            }
            else{
                Node n = new Node(key,value,1);
                map.put(key, n);
                tree.add(n);
            }
        }
        
        class Node{
            int value;
            int key;
            int count;
            long timestamp;
            Node(int key, int value, int count){
                this.key= key;
                this.value = value;
                this.count = count;
                this.timestamp = System.nanoTime();
            }
            public void increment(){
                this.timestamp = System.nanoTime();
                count++;
            }
            public int getCount(){
                return count;
            }
            
            public String toString(){
                return this.key + "," + this.value + "," + this.count;
            }
        }
    }
    
    /**
     * Your LFUCache object will be instantiated and called as such:
     * LFUCache obj = new LFUCache(capacity);
     * int param_1 = obj.get(key);
     * obj.set(key,value);
     */
    

Log in to reply
 

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