Java implementation with HashSet and PriorityQueue


  • 3
    T

    class Entry implements Comparable<Entry> {

    int key, value;
    long lastVisit;
    
    Entry(int key, int value, long lastVisit) {
        this.key = key;
        this.value = value;
        this.lastVisit = lastVisit;
    }
    
    public int compareTo(Entry entry) {
        return (int)(lastVisit - entry.lastVisit);
    }
    

    }

    public class LRUCache {

    PriorityQueue<Entry> queue;
    HashMap<Integer, Entry> map;
    long clock = 0;
    int capacity;
    
    public LRUCache(int capacity) {
        queue = new PriorityQueue<Entry>(capacity);
        map = new HashMap<Integer, Entry>(capacity);
        this.capacity = capacity;
    }
    
    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        
        Entry entry = map.get(key);
        queue.remove(entry);
        entry.lastVisit = clock++;
        queue.add(entry);
        
        return entry.value;
    }
    
    public void set(int key, int value) {
        if (map.containsKey(key)) {
            queue.remove(map.get(key));
        }
        
        Entry entry = new Entry(key, value, clock++);
        if (queue.size() == capacity) {
            Entry toRemove = queue.poll();
            map.remove(toRemove.key);
        }
        
        map.put(key, entry);
        queue.add(entry);
    }
    

    }


Log in to reply
 

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