算法就像搭乐高：手撸 LFU 算法
Note
网站新增大量习题，新增排序算法专题及可视化，具体请查看 网站更新日志~
读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
| LeetCode | 力扣 | 难度 |
|---|---|---|
| 460. LFU Cache | 460. LFU 缓存 | 🔴 |
上篇文章 带你手写LRU算法 写了 LRU 缓存淘汰算法的实现方法，本文来写另一个著名的缓存淘汰算法：LFU 算法。
LRU 算法的淘汰策略是 Least Recently Used，也就是每次淘汰那些最久没被使用的数据；而 LFU 算法的淘汰策略是 Least Frequently Used，也就是每次淘汰那些使用次数最少的数据。
LRU 算法的核心数据结构是使用哈希链表 LinkedHashMap，首先借助链表的有序性使得链表元素维持插入顺序，同时借助哈希映射的快速访问能力使得我们可以在 O(1) 时间访问链表的任意元素。
从实现难度上来说，LFU 算法的难度大于 LRU 算法，因为 LRU 算法相当于把数据按照时间排序，这个需求借助链表很自然就能实现，你一直从链表头部加入元素的话，越靠近头部的元素就是新的数据，越靠近尾部的元素就是旧的数据，我们进行缓存淘汰的时候只要简单地将尾部的元素淘汰掉就行了。
而 LFU 算法相当于是把数据按照访问频次进行排序，这个需求恐怕没有那么简单，而且还有一种情况，如果多个数据拥有相同的访问频次，我们就得删除最早插入的那个数据。也就是说 LFU 算法是淘汰访问频次最低的数据，如果访问频次最低的数据有多条，需要淘汰最旧的数据。
所以说 LFU 算法是要复杂很多的，而且经常出现在面试中，因为 LFU 缓存淘汰算法在工程实践中经常使用，也有可能是因为 LRU 算法太简单了。不过话说回来，这种著名的算法的套路都是固定的，关键是由于逻辑较复杂，不容易写出漂亮且没有 bug 的代码。
那么本文我就带你拆解 LFU 算法，自顶向下，逐步求精，就是解决复杂问题的不二法门。
一、算法描述
要求你写一个类，接受一个 capacity 参数，实现 get 和 put 方法：
class LFUCache {
// 构造容量为 capacity 的缓存
public LFUCache(int capacity) {}
// 在缓存中查询 key
public int get(int key) {}
// 将 key 和 val 存入缓存
public void put(int key, int val) {}
}class LFUCache {
public:
// 构造容量为 capacity 的缓存
LFUCache(int capacity) {}
// 在缓存中查询 key
int get(int key) {}
// 将 key 和 val 存入缓存
void put(int key, int val) {}
};class LFUCache:
def __init__(self, capacity: int):
# 构造容量为 capacity 的缓存
pass
def get(self, key: int) -> int:
# 在缓存中查询 key
pass
def put(self, key: int, val: int) -> None:
# 将 key 和 val 存入缓存
passtype LFUCache struct {
}
// 构造容量为 capacity 的缓存
func Constructor(capacity int) *LFUCache {
return &LFUCache{}
}
// Get 从缓存中查询 key，并返回其对应的值。如果key不存在，则返回 -1。
func (c *LFUCache) Get(key int) int {
return 0
}
// Put 将 key 和 value 存入缓存中。如果容量已满，则需要删除缓存中最近最少使用的元素
func (c *LFUCache) Put(key int, value int) {
}var LFUCache = function (capacity) {
// 构造容量为 capacity 的缓存
}
LFUCache.prototype.get = function (key) {
// 在缓存中查询 key
}
LFUCache.prototype.put = function (key, val) {
// 将 key 和 val 存入缓存
}get(key) 方法会去缓存中查询键 key，如果 key 存在，则返回 key 对应的 val，否则返回 -1。
put(key, value) 方法插入或修改缓存。如果 key 已存在，则将它对应的值改为 val；如果 key 不存在，则插入键值对 (key, val)。
当缓存达到容量 capacity 时，则应该在插入新的键值对之前，删除使用频次（后文用 freq 表示）最低的键值对。如果 freq 最低的键值对有多个，则删除其中最旧的那个。
// 构造一个容量为 2 的 LFU 缓存
LFUCache cache = new LFUCache(2);
// 插入两对 (key, val)，对应的 freq 为 1
cache.put(1, 10);
cache.put(2, 20);
// 查询 key 为 1 对应的 val
// 返回 10，同时键 1 对应的 freq 变为 2
cache.get(1);
// 容量已满，淘汰 freq 最小的键 2
// 插入键值对 (3, 30)，对应的 freq 为 1
cache.put(3, 30);
// 键 2 已经被淘汰删除，返回 -1
cache.get(2);// 构造一个容量为 2 的 LFU 缓存
LFUCache cache(2);
// 插入两对 (key, val)，对应的 freq 为 1
cache.put(1, 10);
cache.put(2, 20);
// 查询 key 为 1 对应的 val
// 返回 10，同时键 1 对应的 freq 变为 2
cache.get(1);
// 容量已满，淘汰 freq 最小的键 2
// 插入键值对 (3, 30)，对应的 freq 为 1
cache.put(3, 30);
// 键 2 已经被淘汰删除，返回 -1
cache.get(2);# 构造一个容量为 2 的 LFU 缓存
cache = LFUCache(2)
# 插入两对 (key, val)，对应的 freq 为 1
cache.put(1, 10)
cache.put(2, 20)
# 查询 key 为 1 对应的 val
# 返回 10，同时键 1 对应的 freq 变为 2
cache.get(1)
# 容量已满，淘汰 freq 最小的键 2
# 插入键值对 (3, 30)，对应的 freq 为 1
cache.put(3, 30)
# 键 2 已经被淘汰删除，返回 -1
cache.get(2)// 构造一个容量为 2 的 LFU 缓存
cache := Constructor(2)
// 插入两对 (key, val)，对应的 freq 为 1
cache.Put(1, 10)
cache.Put(2, 20)
// 查询 key 为 1 对应的 val
// 返回 10，同时键 1 对应的 freq 变为 2
cache.Get(1)
// 容量已满，淘汰 freq 最小的键 2
// 插入键值对 (3, 30)，对应的 freq 为 1
cache.Put(3, 30)
// 键 2 已经被淘汰删除，返回 -1
cache.Get(2)// 构造一个容量为 2 的 LFU 缓存
var cache = new LFUCache(2);
// 插入两对 (key, val)，对应的 freq 为 1
cache.put(1, 10);
cache.put(2, 20);
// 查询 key 为 1 对应的 val
// 返回 10，同时键 1 对应的 freq 变为 2
cache.get(1);
// 容量已满，淘汰 freq 最小的键 2
// 插入键值对 (3, 30)，对应的 freq 为 1
cache.put(3, 30);
// 键 2 已经被淘汰删除，返回 -1
cache.get(2);二、思路分析
一定先从最简单的开始，根据 LFU 算法的逻辑，我们先列举出算法执行过程中的几个显而易见的事实：
1、调用 get(key) 方法时，要返回该 key 对应的 val。
2、只要用 get 或者 put 方法访问一次某个 key，该 key 的 freq 就要加一。
3、如果在容量满了的时候进行插入，则需要将 freq 最小的 key 删除，如果最小的 freq 对应多个 key，则删除其中最旧的那一个。
好的，我们希望能够在 O(1) 的时间内解决这些需求，可以使用基本数据结构来逐个击破：
1、使用一个 HashMap 存储 key 到 val 的映射，就可以快速计算 get(key)。
HashMap<Integer, Integer> keyToVal;unordered_map<int, int> keyToVal;keyToVal = {}keyToVal := make(map[int]int)var keyToVal = new Map();2、使用一个 HashMap 存储 key 到 freq 的映射，就可以快速操作 key 对应的 freq。
HashMap<Integer, Integer> keyToFreq;unordered_map<int, int> keyToFreq;keyToFreq = {}keyToFreq := make(map[int]int)var keyToFreq = new Map();3、这个需求应该是 LFU 算法的核心，所以我们分开说：