📃 题目描述

题目链接：

• 设计LFU缓存结构_牛客题霸_牛客网 (nowcoder.com) (opens new window)

🔔 解题思路

双哈希表

第一个哈希表存储节点的 key-value

第二个哈希表存储 key 对应出现的频率（另外，这里需要注意的是，题目要求：如果调用次数最少的key有多个，上次调用发生最早的 key 被删除）

自己实现 HashMap

具体思路可以参考 BM101 设计 LFU 缓存结构 (opens new window)

• TODO

LinkedHashMap

可以用 LinkedHashMap（accessOrder = true） 按照访问顺序排序的特性存储 key 对应的频率：即调用 get 方法后，会将这次访问的元素移至链表尾部，不断访问可以形成按访问顺序排序的链表（题目要求：如果调用次数最少的 key 有多个，上次调用发生最早的 key 被删除）

import java.util.*;


public class Solution {
    /**
     * lfu design
     * @param operators int整型二维数组 ops
        - operaotrs[0] 表示是 set 操作还是 get 操作
        - operators[1] operators[2] 表示 key-value
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public int[] LFU (int[][] operators, int k) {
        // 存储 get 返回的结果
        List<Integer> list = new ArrayList<>();
        
        // key-value
        Map<Integer, Integer> map = new HashMap<>();
        // key-key 出现的频率
        Map<Integer, Integer> freqMap = new LinkedHashMap<>(16, 0.75f, true);
        
        for (int[] operator : operators) {
            int key = operator[1];
            
            // set
            if (operator[0] == 1) {
                int value = operator[2];
                // 已经使⽤过该 key，map 替换
                if (map.containsKey(key)) {
                    map.put(key, value);
                    freqMap.put(key, freqMap.get(key) + 1);
                }
                // 第⼀次使⽤到这个 key，需要判断 map 容量
                else {
                    // 超过了最大容量，则删除频率最低的记录
                    if (map.size() == k) {
                        int removeKey = getMinKey(freqMap);
                        map.remove(removeKey);
                        freqMap.remove(removeKey);
                    }
                    // 更新 map 和 freqMap
                    map.put(key, value);
                    freqMap.put(key, freqMap.getOrDefault(key, 0) + 1);
                }
            }
            // get
            else if (operator[0] == 2) {
                // key 不存在，返回 -1
                if (!map.containsKey(key)) {
                    list.add(-1);
                }
                // key 存在，更新 freqMap
                else {
                    freqMap.put(key, freqMap.get(key) + 1);
                    list.add(map.get(key));
                }
            }
        }
        
        
        // list -> res
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i ++) {
            res[i] = list.get(i);
        }
        return res;
    }
    
    // 获取频率最低的 key
    // 题目要求：如果调用次数最少的 key 有多个，上次调用发生最早的 key 被删除
    private int getMinKey(Map<Integer, Integer> freqMap) {
        int minCount = Integer.MAX_VALUE;
        int key = 0;
        for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
            // 只有小于的时候才更新 key, 这样，频率相等的时候，取到的就是第一个出现该频率的 key
            // 也就是上次调用发生最早的 key（因为发生调用的时间越早，就越排在 LinkedHashMap 的前面）
            if (entry.getValue() < minCount) {
                minCount = entry.getValue();
                key = entry.getKey();
            }
        }
        return key;
    }
}

自己实现 LinkedHashMap

• TODO

💥 复杂度分析

• 空间复杂度：
• 时间复杂度：