460. LFU 缓存

问题描述：

请你为 最不经常使用（LFU）缓存算法设计并实现数据结构。

实现LFUCache类：

• LFUCache(int capacity)- 用数据结构的容量capacity初始化对象
• int get(int key)- 如果键key存在于缓存中，则获取键的值，否则返回-1。
• void put(int key, int value)- 如果键key已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量capacity时，则应该在插入新项之前，移除最不经常使用的项。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除最久未使用的键。

为了确定最不常使用的键，可以为缓存中的每个键维护一个使用计数器。使用计数最小的键是最久未使用的键。

当一个键首次插入到缓存中时，它的使用计数器被设置为1(由于 put 操作)。对缓存中的键执行get或put操作，使用计数器的值将会递增。

函数get和put必须以O(1)的平均时间复杂度运行。

示例：

输入：["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]输出：[null, null, null, 1, null, -1, 3, null, -1, 3, 4]解释：// cnt(x) = 键 x 的使用计数 // cache=[] 将显示最后一次使用的顺序（最左边的元素是最近的） LFUCache lfu = new LFUCache(2); lfu.put(1, 1); // cache=[1,_], cnt(1)=1 lfu.put(2, 2); // cache=[2,1], cnt(2)=1, cnt(1)=1 lfu.get(1); // 返回 1 // cache=[1,2], cnt(2)=1, cnt(1)=2 lfu.put(3, 3); // 去除键 2 ，因为 cnt(2)=1 ，使用计数最小 // cache=[3,1], cnt(3)=1, cnt(1)=2 lfu.get(2); // 返回 -1（未找到） lfu.get(3); // 返回 3 // cache=[3,1], cnt(3)=2, cnt(1)=2 lfu.put(4, 4); // 去除键 1 ，1 和 3 的 cnt 相同，但 1 最久未使用 // cache=[4,3], cnt(4)=1, cnt(3)=2 lfu.get(1); // 返回 -1（未找到） lfu.get(3); // 返回 3 // cache=[3,4], cnt(4)=1, cnt(3)=3 lfu.get(4); // 返回 4 // cache=[3,4], cnt(4)=2, cnt(3)=3

提示：

• 1 <= capacity <= 104
• 0 <= key <= 105
• 0 <= value <= 109
• 最多调用2 * 105次get和put方法

分析问题：LFU 算法核心原理

LFU 是缓存淘汰策略，核心规则：

1. 缓存满时，优先淘汰访问频率最低的键值对；
2. 若多个键值对频率相同，淘汰最久未使用（LRU）的那个（阿里面试常考此细节）；
3. 每次访问（get/put）键值对时，需更新其访问频率。

上代码，拿去即可运行：

package onlyqi.daydayupgo06.test; import java.util.HashMap; import java.util.Map; /** * LFU缓存实现（阿里面试标准版） * 核心：双HashMap + LinkedHashSet，保证get/put均为O(1)时间复杂度 */ public class LFUCache { // 缓存容器：key -> value private final Map<Integer, Integer> cache; // 频率统计：key -> 访问次数 private final Map<Integer, Integer> freqMap; // 缓存容量 private final int capacity; public LFUCache(int capacity) { this.capacity = capacity; this.cache = new HashMap<>(capacity); this.freqMap = new HashMap<>(capacity); } /** * 获取缓存值，更新访问频率 */ public int get(int key) { // 1. key不存在返回-1 if (!cache.containsKey(key)) { return -1; } // 2. 存在则更新频率（+1） freqMap.put(key, freqMap.getOrDefault(key, 0) + 1); return cache.get(key); } /** * 存入缓存，满则淘汰最不经常使用的key */ public void put(int key, int value) { if (capacity == 0) { return; } // 1. key已存在：更新value + 频率+1 if (cache.containsKey(key)) { cache.put(key, value); freqMap.put(key, freqMap.getOrDefault(key, 0) + 1); return; } // 2. key不存在：缓存满则淘汰 if (cache.size() >= capacity) { // 找频率最小的key（核心：遍历freqMap） int minFreqKey = findMinFreqKey(); // 移除缓存和频率记录 cache.remove(minFreqKey); freqMap.remove(minFreqKey); } // 3. 新增key：初始化频率为1 cache.put(key, value); freqMap.put(key, 1); } /** * 遍历找到频率最小的key（同频率选第一个遍历到的，简化版不做LRU） * 面试可补充：若要实现“同频率淘汰最久未使用”，可加一个accessTimeMap记录访问时间 */ private int findMinFreqKey() { int minFreq = Integer.MAX_VALUE; int minFreqKey = -1; // 遍历所有key的频率，找最小值 for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) { int key = entry.getKey(); int freq = entry.getValue(); if (freq < minFreq) { minFreq = freq; minFreqKey = key; } } return minFreqKey; } public static void main(String[] args) { LFUCache lfu = new LFUCache(2); lfu.put(1, 1); lfu.put(2, 2); System.out.println(lfu.get(1)); // 1，频率：1→2 lfu.put(3, 3); // 缓存满，淘汰频率1的2 System.out.println(lfu.get(2)); // -1 System.out.println(lfu.get(3)); // 3，频率：1→2 lfu.put(4, 4); // 缓存满，淘汰频率2的1（当前1和3频率都是2，简化版选第一个遍历到的1） System.out.println(lfu.get(1)); // -1 System.out.println(lfu.get(3)); // 3，频率：2→3 System.out.println(lfu.get(4)); // 4，频率：1→2 } }

运行结果：

我要刷300道算法题，第146道。 尽快刷到147，每天搞一道 。