题解 | #设计LFU缓存结构#

import java.util.*;


public class Solution {
    /**
     * lfu design
     * @param operators int整型二维数组 ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    HashMap<Integer,Integer> keyToValue;
    HashMap<Integer,Integer> keyToFreq;
    HashMap<Integer,LinkedHashSet<Integer>> freqToKeys; 
    int minFreq;
    int cap;
    public int[] LFU (int[][] operators, int k) {
        // write code here
        ArrayList<Integer> resList = new ArrayList<>();
        keyToValue = new HashMap<>();
        keyToFreq = new HashMap<>();
        freqToKeys = new HashMap<>();
        minFreq = 0;
        cap = k;
        
        int m = operators.length;
        for(int i=0;i<m;i++){
            if(operators[i][0] == 1){
                put(operators[i][1],operators[i][2]);
            }else{
                int res = get(operators[i][1]);
                resList.add(res);
            }
        }
        int l = resList.size();
        int[] resArr = new int[l];
        for(int i = 0;i<l;i++){
            resArr[i] = resList.get(i);
        }
        return resArr;
        
    }
    public int get(int key){
            if(!keyToValue.containsKey(key)){
                return -1;
            }
            increFreq(key);
            return keyToValue.get(key);
        }
        private void increFreq(int key){
            int freq = keyToFreq.get(key);
            keyToFreq.put(key,freq+1);
            freqToKeys.get(freq).remove(key);
            freqToKeys.putIfAbsent(freq+1,new LinkedHashSet<Integer>());
            freqToKeys.get(freq+1).add(key);
            if(freqToKeys.get(freq).isEmpty()){
                freqToKeys.remove(freq);
               if(freq == this.minFreq){
                   this.minFreq++;
               } 
            }
        }
        
        public void put(int key,int value){
            if(this.cap <= 0)
                return;
            if(keyToValue.containsKey(key)){
                keyToValue.put(key,value);
                increFreq(key);
                return;
            }else{
                if(this.cap <= keyToValue.size()){
                    removeMinFreqKey();
                }
                keyToValue.put(key,value);
                keyToFreq.put(key,1);
                freqToKeys.putIfAbsent(1,new LinkedHashSet<>());
                freqToKeys.get(1).add(key);
                this.minFreq = 1;
            }
        }
        
        private void removeMinFreqKey(){
            LinkedHashSet<Integer> keyList = freqToKeys.get(this.minFreq);
            int deleteKey = keyList.iterator().next();
            keyList.remove(deleteKey);
            if(keyList.isEmpty()){
                freqToKeys.remove(this.minFreq);
            }
            keyToValue.remove(deleteKey);
            keyToFreq.remove(deleteKey);
        }
}