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

import java.util.*;


public class Solution {
    
    LinkedHashMap<Integer, Integer> container = null; // 容器，用于存放 (key, value)
    LinkedHashMap<Integer, Integer> keyOperations = null; // 记录每一条 key 的操作次数
    int sz; // container 的容量
    
    public class ComparaKey implements Comparator<Integer> {
        @Override
        public int compare(Integer num1, Integer num2) {
            return keyOperations.get(num1) - keyOperations.get(num2);
        }
    }
    
    /**
     * lfu design
     * @param operators int整型二维数组 ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public int[] LFU (int[][] operators, int k) {
        // write code here
        // 初始化容器
        container = new LinkedHashMap<>(k);
        keyOperations = new LinkedHashMap<>(k);
        sz = k;
        ArrayList<Integer> arrayList = new ArrayList<>();
        
        for (int[] operator : operators) {
            int op = operator[0];
            if (op == 1) {
                set(operator[1], operator[2]);
            }
            else {
                int tmprs = get(operator[1]);
                arrayList.add(tmprs);
            }
        }
        
        return arrayList.stream().mapToInt(Integer::intValue).toArray();
    }
    
    public int get(int key) {
        int value = container.getOrDefault(key, -1);
        
        if (value != -1) {
            container.remove(key, value);
            container.put(key, value);
            // 每次对 key 进行一次操作，都要在 keyOperations 中进行登记
            int num = keyOperations.getOrDefault(key, 0);
            num++; // num++
            keyOperations.put(key, num);
        }
        return value;
    }
    
    public void set(int key, int value) {
        // 判断是插入操作还是更改操作
        int op = container.getOrDefault(key, -1);
        // 更改操作
        if (op != -1) {
            container.remove(key);
            container.put(key, value);
            // 别忘了，每次对 key 进行一次操作，都要在 keyOperations 中进行登记
            int num = keyOperations.getOrDefault(key, 0);
            num++;
            keyOperations.put(key, num);
        }
        // 插入操作
        else {
            // 判断当前容量是否已经达到上限
            int currentSize = container.size();
            if (sz == currentSize) {
                
                int[] keys = container.keySet().stream().sorted(new ComparaKey()).mapToInt(Integer::intValue).toArray();
                Queue<Integer> queue = new LinkedList<>();
                int min = keyOperations.get(keys[0]);
                for (int i = 0; i < keys.length; i++) {
                    if (min == keyOperations.get(keys[i])) {
                        queue.add(keys[i]);
                    }
                    else {
                        break;
                    }
                }
                // Queue，存放了调用次数最少的那一部分 key
                if (queue.size() == 1) {
                    int removeKey = queue.poll();
                    container.remove(removeKey); // 将操作次数最少的 key 从缓存结构中移除
                    container.put(key, value); // 将新的记录添加到缓存结构中
                    
                    keyOperations.remove(removeKey);
                    // 别忘了，每次对 key 进行一次操作，都要在 keyOperations 中进行登记
                    int num = keyOperations.getOrDefault(key, 0);
                    num++;
                    keyOperations.put(key, num);
                }
                else {
                    int removeKey = keys[0];
                    int[] containerKeys = container.keySet().stream().mapToInt(Integer::intValue).toArray();
                    for (int i = 0; i < containerKeys.length; i++) {
                        if (queue.contains(containerKeys[i])) {
                            removeKey = containerKeys[i]; // 如果调用次数最少的 key 有多个，上次调用发生最早的 key 删除
                            break;
                        }
                    }
                    container.remove(removeKey); // 将操作次数最少的 key 从缓存结构中移除
                    container.put(key, value); // 将新的记录添加到缓存结构中
                    
                    keyOperations.remove(removeKey);
                    // 别忘了，每次对 key 进行一次操作，都要在 keyOperations 中进行登记
                    int num = keyOperations.getOrDefault(key, 0);
                    num++;
                    keyOperations.put(key, num);
                }
                
            }
            else {
                container.put(key, value);
                // 别忘了，每次对 key 进行一次操作，都要在 keyOperations 中进行登记
                int num = keyOperations.getOrDefault(key, 0);
                num++;
                keyOperations.put(key, num);
            }
        }
    }
}