Trivial solution inspired by ckcz123


  • 0
    O
    public class LFUCache {
        private int capacity;
        private Map<Integer, CacheEntry> map;
        private Queue<CacheEntry> q;
        private int timestamp = 0;
        public LFUCache(int capacity) {
            this.capacity = capacity;
            map = new HashMap<>();
            q = new PriorityQueue<>(capacity == 0? 1 : capacity, new Comparator<CacheEntry>(){
                public int compare(CacheEntry c1, CacheEntry c2) {
                    if (c1.count != c2.count) {
                        return c1.count - c2.count;
                    }
    
                    return c1.timestamp - c2.timestamp;
                }
            });
        }
    
        public int get(int key) {
            if (map.size() == 0 || !map.containsKey(key)) {
                return -1;
            }
    
            update(key);
            return map.get(key).value;
        }
    
        public void set(int key, int value) {
            if (capacity == 0) return;
            if (map.containsKey(key)) {
                map.get(key).value = value;
                update(key);
                return;
            }
    
            CacheEntry cache = new CacheEntry(key, value, 1, this.timestamp++);
    
            if (map.size() < capacity) {
                map.put(key, cache);
                q.add(cache);
                return;
            }
    
            CacheEntry evict = q.poll();
            map.remove(evict.key);
            map.put(key, cache);
            q.add(cache);
        }
    
        private void update(int key) {
            CacheEntry cache = map.get(key);
            q.remove(cache);
            cache.count++;
            cache.timestamp = timestamp++;
            q.add(cache);
    
        }
    }
    
    class CacheEntry {
        public int count;
        public int timestamp;
        public int key;
        public int value;
    
        public CacheEntry(int key, int value, int count, int timestamp) {
            this.count = count;
            this.value = value;
            this.key = key;
            this.timestamp = timestamp;
        }
    
        public boolean equals(Object cacheEntry) {
            return this.key == ((CacheEntry) cacheEntry).key;
        }
    }
    

  • 0
    V

    I have basically the same code, except that I use a TreeSet instead of your PriorityQueue, which should make queue.remove() an O(logn) operation instead of O(n).

    I still get around 200ms average, because of high constant factors.


Log in to reply
 

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