Share my PriorityQueue Solution


  • 1
    W

    Here I share my solution.
    Since I use priority queue, it's not o(1) for get() and set().
    The basic idea is, for each key-value set, use a var 'frequency' to store the visit frequency, and use priority queue to maintain the ascending order based on frequency.
    One annoying thing is that when 2 or more key-value sets has same frequency, and they are in priority queue somewhere, the key-value sets are not guaranteed to be ordered as most recent order, and this will cause issue if poll from priority queue.
    So my solution, not great here, but still work under testing, is adding a time stamp for each key-value set. The time stamp increases each time when set() or get() get called, and pass it to the time var in key-value set. Then use both frequency and time stamp as compare vars when override the comparator, this will make sure the priority queue keep the right frequency and recent order.

    Here's the code~

    
        class Node{
            int key;
            int value;
            int freq;   // store frequency
            int time;   // store time stamp
        }
        
        private PriorityQueue<Node> pq;    
        private int capacity;
        private int count;
        private int time;           // use for compare if has same frequency, bigger time stamp store further in pq
        private Map<Integer, Node> m;
            
        public LFUCache(int capacity) {
            this.capacity=capacity;
            this.count=0;
            this.time=0;
            if(capacity==0) return;
            this.pq = new PriorityQueue<Node>(capacity, new Comparator<Node>(){
                @Override
                public int compare(Node n1, Node n2){
                    if(n1.freq>n2.freq) return 1;
                    if(n1.freq<n2.freq) return -1;
                    if(n1.freq==n2.freq){
                        return n1.time-n2.time;         // time is key part for sort if 2 has same freq, but it has drawbacks, 2 time stamps can't exceed max Integer, any good ideas? 
                    }
                    return 0;
                }
            });
            this.m = new HashMap<Integer, Node>();
        }
        
        public int get(int key) {
            if(capacity==0) return -1;
            if(!m.containsKey(key)) return -1;
            Node n= m.get(key);
            updateNode(n);      // update the node each time visit
            return n.value;
        }
        
        public void set(int key, int value) {
            if(capacity==0) return;
            if(!m.containsKey(key)){
                if(count>=capacity){
                    Node n = pq.poll();      // remove least frequent one
                    m.remove(n.key);
                    count--;
                }
                Node n = new Node();        // add new one in pq
                n.key=key;
                n.value=value;
                n.freq=1;
                n.time=time++;  // time stamp always +1
                pq.add(n);      // priority queue to store node, based on freq
                count++;
                m.put(key,n);
            }else{
                Node n=m.get(key);
                n.value=value;
                updateNode(n);
            }
        }
        
        private void updateNode(Node n){    // update Node, no matter use get or set function
            this.pq.remove(n);  // remove from pq
            n.freq+=1;
            n.time=this.time++;       // update time stamp
            pq.add(n);      // add again, reset position
        }
    }

Log in to reply
 

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