Simple Java O(1) Solution just using LinkedListHashMap.


  • 0
    S
    public class LFUCache {
    class LFU {
       int value;
       int frequency;
        public LFU(int val,int freq){
            value=val;
            frequency=freq;
        }
    };
     int cap;
    LinkedHashMap<Integer,LFU> map;
    int lastKey; 
        public LFUCache(int capacity) {
            cap=capacity;
            map=new LinkedHashMap<Integer,LFU>(cap,1.0f,true);
            lastKey=0;
        }
        
        public int get(int key) {
            if(map.get(key)==null)return -1;
            LFU obj=map.get(key);
            obj.frequency++;
            map.put(key,obj);
            return map.get(key).value;
        }
        
        public void put(int key, int value) {
          
          if(map.get(key)!=null){
              LFU obj=map.get(key);
            obj.frequency++;
              obj.value=value;
            map.put(key,obj);
          }
            else{
                LFU obj = new LFU(value,1);
                map.put(key,obj);
                lastKey=key;
            }
            if(map.size()>cap) {
                int keyDel=findFreqEntry(map);
                map.remove(keyDel);
            } 
          
        }
        int findFreqEntry(LinkedHashMap<Integer,LFU> map){
            int minKey=0;
            int minFreq=Integer.MAX_VALUE;
         /*   for(int key:map.keySet()){
                LFU obj=map.get(key);
                if(minFreq>obj.frequency){
                    minKey=key;
                    minFreq=obj.frequency;
                }
            }*/
            for(Map.Entry<Integer, LFU> entry : map.entrySet())
            {
                if(minFreq > entry.getValue().frequency && entry.getKey()!=lastKey)
                {
                    minKey = entry.getKey();
                    minFreq = entry.getValue().frequency;
                }           
            }
            System.out.println(minKey);
            return minKey;
        }
    }

  • 0
    S

    Pardon the title *LinkedHashMap


Log in to reply
 

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