LFU缓存

题目描述：力扣

解题思路：定义一个Map<Integer, int[]> dictionary; 数组的长度为3，index=0的位置存储value值，index=1的位置存储操作次数，index=2的位置存储最近一次操作的编号(cnt)。

class LFUCache {
    int cnt = 0;//操作编号，无论是put操作还是get操作都会加1
    int capacity = 0;//容量
    Map<Integer, int[]> dictionary;
    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.dictionary = new HashMap<>(capacity);
    }
    
    public int get(int key) {
        if(this.capacity == 0)
            return -1;
        int[] sb = this.dictionary.get(key);
        if(null == sb){
            return -1;
        }
        else{
            sb[1]++;
            sb[2]=cnt++;
            return sb[0];
        }
    }
    
    public void put(int key, int value) {
        if(this.capacity==0)
            return;
        if(null !=this.dictionary.get(key)){
            this.dictionary.get(key)[0]=value;
            this.dictionary.get(key)[1]++;
            this.dictionary.get(key)[2]=cnt++;
            return;
        }
        if(this.dictionary.size()<this.capacity){
            int[] temp = new int[]{value,0,cnt++};
            this.dictionary.put(key, temp);
        }
        else{
            int min_cnt = Integer.MAX_VALUE;//操作次数
            int min_key = 0;//记录操作次数最小且操作编号最小的键
            int recent_num = 0;//操作编号
            for(Map.Entry<Integer, int[]> entry: dictionary.entrySet()){
                if(entry.getValue()[1]<min_cnt){
                    min_cnt = entry.getValue()[1];
                    min_key = entry.getKey();
                    recent_num = entry.getValue()[2];
                }
                else if(entry.getValue()[1]==min_cnt && entry.getValue()[2]<recent_num){
                    min_key = entry.getKey();
                    recent_num = entry.getValue()[2];
                }
                else{
                    continue;
                }
            }
            this.dictionary.remove(min_key);
            int[] temp = new int[]{value,0,cnt++};
            this.dictionary.put(key, temp);
        }
    }
}

/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache obj = new LFUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */