Java O(1) solution using ArrayList and HashMap only


  • 0
    H

    The basic idea is to partition the frequency into buckets, each bucket is implemented as Queue, so least used item is always at the last one.

    public class LFUCache {
        ArrayList<LinkedList<Integer>> FrequencyBuckets = null; 
        HashMap<Integer,Pair> map = null;
        int count = 0;
        int capacity = 0;
        public LFUCache(int capacity) {
            FrequencyBuckets = new ArrayList<LinkedList<Integer>>();
            FrequencyBuckets.add(new LinkedList<Integer>());
            map = new HashMap<>(capacity);
            this.capacity = capacity;
        }
        
        public int get(int key) {
            Pair p = map.get(key);
            if(p!=null){
                IncreFrequency(p,key);
                return p.value;
            }
            return -1;
        }
        
        public void put(int key, int value) {
            
            if(capacity==0) return;
            Pair p = null;
            if((p = map.get(key))!=null){
                p.value = value;
                IncreFrequency(p,key);
                return;
            }
            if(count==capacity){
                LinkedList<Integer> ll = null;
                int i = 0;
                while((ll = FrequencyBuckets.get(i)).size()==0){i++;}
                Integer vv = ll.pollLast();
                Pair pp = map.get(vv);
                map.remove(vv);
                count--;
            }
            
            map.put(key,new Pair(value));
            FrequencyBuckets.get(0).addFirst(key);
            count++;
            
        }
        
        private void IncreFrequency(Pair p,int key){
            FrequencyBuckets.get(p.frequency).removeFirstOccurrence(key);
                p.frequency++;
                if(p.frequency >= FrequencyBuckets.size())  FrequencyBuckets.add(new LinkedList<Integer>());
                FrequencyBuckets.get(p.frequency).addFirst(key);
        }
        
        class Pair{
            public int value = 0;
            public int frequency = 0;
            public Pair(int val){
                value = val;
            }
        }
    }
    
    /**
     * Your LFUCache object will be instantiated and called as such:
     * LFUCache obj = new LFUCache(capacity);
     * int param_1 = obj.get(key);
     * obj.put(key,value);
     */
    

Log in to reply
 

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