Share my concise Java solution


  • 0
    public class LFUCache {
    
    	int maxsize;
    	int timestamp;
    	
    	Map<Integer, Tuple> map = new HashMap<Integer, Tuple>();
    	PriorityQueue<Tuple> queue = new PriorityQueue<Tuple>();
    	
        public LFUCache(int capacity) {
            maxsize = capacity;
            timestamp = 0;
        }
        
        public int get(int key) {
            if (maxsize == 0) return -1;
        	timestamp ++;
            if(map.containsKey(key)){
            	Tuple tuple = map.get(key);
            	tuple.timestamp = timestamp;
            	tuple.freq ++;
            	queue.remove(tuple);
            	queue.offer(tuple);
            	return tuple.val;
            }
            else{
            	return -1;
            }
        }
        
        public void set(int key, int value) {
            if (maxsize == 0) return;
        	timestamp ++;
            if(map.containsKey(key)){
            	Tuple tuple = map.get(key);
            	tuple.timestamp = timestamp;
            	tuple.freq ++;
            	tuple.val = value;
            	queue.remove(tuple);
            	queue.offer(tuple);
            }
            else{
            	if(map.size() == maxsize){
            		Tuple tuple = queue.poll();
            		int deletekey = tuple.key;
            		map.remove(deletekey);        		
            	}       	
            	Tuple newTuple = new Tuple(key, value, 1, timestamp);
        		map.put(key, newTuple);
        		queue.offer(newTuple);
            }
        }
    }
    
    class Tuple implements Comparable<Tuple>{
    	int key;
    	int val;
    	int freq;
    	int timestamp;
    	
    	public Tuple(int key, int val, int freq, int timestamp){
    		this.key = key;
    		this.val = val;
    		this.freq = freq;
    		this.timestamp = timestamp;
    	}
    	
    	public int compareTo(Tuple that){
    		if(this.freq == that.freq){
    			return this.timestamp - that.timestamp;
    		}
    		else{
    			return this.freq - that.freq;
    		}
    	}
    }
    

Log in to reply
 

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