My Java Solution


  • 0
    R
    class Wrapper{
        int value, freq = 1;
        Wrapper(int value){
            this.value = value;
        }
    }
    public class LFUCache {
        private Map<Integer, Wrapper> valMap;
        private Map<Integer, Set<Integer>> freqMap;
        private int capacity, minFreq;
        public LFUCache(int capacity) {
            valMap = new HashMap<Integer, Wrapper>();
            freqMap = new HashMap<Integer, Set<Integer>>();
            this.capacity = capacity;
            minFreq = 1;
        }
        public void update(int key, int freq){
            if(!freqMap.containsKey(freq)){
                freqMap.put(freq, new LinkedHashSet<Integer>());
            }
            //if(freq != 1 && freqMap.get(freq - 1).contains(key)){
            if(freq != 1){
                freqMap.get(freq - 1).remove(key);
            }
            freqMap.get(freq).add(key);
        }
        public int get(int key) {
            Wrapper w = valMap.get(key);
            if(w != null){
                int freq = w.freq;
                if(freq == minFreq && freqMap.get(minFreq).size() == 1) minFreq++;
                w.freq++;
                update(key, w.freq);
                return w.value;
            }
            return -1;
        }
        
        public void put(int key, int value) {
            if(valMap.containsKey(key)){
                valMap.get(key).value = value;
                get(key);
            }
            else{
                Wrapper w = new Wrapper(value);
                valMap.put(key, w);
                update(key, 1);
                if(valMap.size() > capacity){
                    int byeKey = freqMap.get(minFreq).iterator().next();
                    valMap.remove(byeKey);
                    freqMap.get(minFreq).remove(byeKey);
                }
                minFreq = 1;
            }
        }
    }
    

Log in to reply
 

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