460. LFU 缓存
题目描述
实现一个按“最不经常使用”（LFU）策略淘汰的缓存类 LFUCache。每个键都附带一个使用次数：首次通过 put 放入时记为 1，之后每次对它调用 get 或 put 都加 1。
LFUCache(capacity)：创建容量为 capacity 的缓存。get(key)：键存在时返回对应的值，否则返回 -1。
put(key, value)：键已存在就改写它的值；不存在就插入。如果插入前缓存已经装满，先移除使用次数最少的键；若有多个键次数并列最少，移除其中最久没被访问的那个。put 无返回值。
get 和 put 的平均时间复杂度都要求是 O(1)。
示例 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]
解释：容量为 2。放入 3 时淘汰次数最少的键 2；放入 4 时键 1 和 3 次数都是 2，淘汰较久未用的键 1，所以之后 get(1) 和 get(2) 都返回 -1。
数据范围
1 <= capacity <= 10^40 <= key <= 10^50 <= value <= 10^9get与put合计调用不超过2 * 10^5次。
解题思路：哈希表 + 按频率分组的有序链表
维护三张表和一个变量：val 存值，cnt 存使用次数，groups[f] 是使用次数为 f 的键组成的有序集合（按最近使用时间排列，最久的在前），minf 是当前最小使用次数。一次使用（touch）把键从 groups[f] 移到 groups[f+1] 的末尾；如果 groups[minf] 因此变空，minf 加 1。插入新键时如果满了，淘汰 groups[minf] 的第一个键；新键次数为 1，所以 minf 重置为 1。
为什么正确
每个键恰好在 groups[cnt[key]] 中；各组内部按最近使用时间从旧到新；minf 是非空组中最小的次数。
复杂度分析
get 和 put 均为 O(1)；空间 O(capacity)。
易错点
更新已有键的值也要算一次使用；插入新键前要先淘汰再把 minf 置为 1，顺序反了会淘汰错组；touch 时只有当变空的是 groups[minf] 才能让 minf 加 1。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class LFUCache:
def __init__(self, capacity: int = 2):
self.cap = capacity
self.val = {}
self.cnt = {}
self.groups = {}
self.minf = 0
def _touch(self, key: int) -> None:
f = self.cnt[key]
del self.groups[f][key]
if not self.groups[f]:
del self.groups[f]
if self.minf == f:
self.minf = f + 1
self.cnt[key] = f + 1
self.groups.setdefault(f + 1, {})[key] = None
def get(self, key: int) -> int:
if key not in self.val:
return -1
self._touch(key)
return self.val[key]
def put(self, key: int, value: int) -> None:
if key in self.val:
self.val[key] = value
self._touch(key)
return
if len(self.val) == self.cap:
old = next(iter(self.groups[self.minf]))
del self.groups[self.minf][old]
if not self.groups[self.minf]:
del self.groups[self.minf]
del self.val[old]
del self.cnt[old]
self.val[key] = value
self.cnt[key] = 1
self.groups.setdefault(1, {})[key] = None
self.minf = 1class LFUCache {
private int cap, minf;
private Map<Integer, Integer> val, cnt;
private Map<Integer, LinkedHashSet<Integer>> groups;
public LFUCache(int capacity) {
cap = capacity;
val = new HashMap<>();
cnt = new HashMap<>();
groups = new HashMap<>();
minf = 0;
}
private void touch(int key) {
int f = cnt.get(key);
groups.get(f).remove(key);
if (groups.get(f).isEmpty()) {
groups.remove(f);
if (minf == f) {
minf = f + 1;
}
}
cnt.put(key, f + 1);
groups.computeIfAbsent(f + 1, k -> new LinkedHashSet<>()).add(key);
}
public int get(int key) {
if (!val.containsKey(key)) {
return -1;
}
touch(key);
return val.get(key);
}
public void put(int key, int value) {
if (val.containsKey(key)) {
val.put(key, value);
touch(key);
return;
}
if (val.size() == cap) {
int old = groups.get(minf).iterator().next();
groups.get(minf).remove(old);
if (groups.get(minf).isEmpty()) {
groups.remove(minf);
}
val.remove(old);
cnt.remove(old);
}
val.put(key, value);
cnt.put(key, 1);
groups.computeIfAbsent(1, k -> new LinkedHashSet<>()).add(key);
minf = 1;
}
}class LFUCache {
public:
int cap, minf;
unordered_map<int, int> val, cnt;
unordered_map<int, list<int>> groups;
unordered_map<int, list<int>::iterator> pos;
LFUCache(int capacity) {
cap = capacity;
val.clear();
cnt.clear();
groups.clear();
minf = 0;
}
void touch(int key) {
int f = cnt[key];
groups[f].erase(pos[key]);
if (groups[f].empty()) {
groups.erase(f);
if (minf == f) {
minf = f + 1;
}
}
cnt[key] = f + 1;
groups[f + 1].push_back(key);
pos[key] = prev(groups[f + 1].end());
}
int get(int key) {
if (!val.count(key)) {
return -1;
}
touch(key);
return val[key];
}
void put(int key, int value) {
if (val.count(key)) {
val[key] = value;
touch(key);
return;
}
if ((int) val.size() == cap) {
int old = groups[minf].front();
groups[minf].pop_front();
if (groups[minf].empty()) {
groups.erase(minf);
}
val.erase(old);
cnt.erase(old);
pos.erase(old);
}
val[key] = value;
cnt[key] = 1;
groups[1].push_back(key);
pos[key] = prev(groups[1].end());
minf = 1;
}
};type lfuNode struct {
key int
prev, next *lfuNode
}
type LFUCache struct {
cap, minf int
val, cnt map[int]int
groups map[int]*lfuNode
node map[int]*lfuNode
}
func Constructor(capacity int) LFUCache {
c := LFUCache{cap: capacity}
c.val = map[int]int{}
c.cnt = map[int]int{}
c.groups = map[int]*lfuNode{}
c.node = map[int]*lfuNode{}
c.minf = 0
return c
}
func (this *LFUCache) appendTo(f int, n *lfuNode) {
head, ok := this.groups[f]
if !ok {
head = &lfuNode{}
head.prev, head.next = head, head
this.groups[f] = head
}
n.prev, n.next = head.prev, head
head.prev.next = n
head.prev = n
}
func (this *LFUCache) touch(key int) {
f := this.cnt[key]
n := this.node[key]
n.prev.next, n.next.prev = n.next, n.prev
if head := this.groups[f]; head.next == head {
delete(this.groups, f)
if this.minf == f {
this.minf = f + 1
}
}
this.cnt[key] = f + 1
this.appendTo(f+1, n)
}
func (this *LFUCache) Get(key int) int {
if _, ok := this.val[key]; !ok {
return -1
}
this.touch(key)
return this.val[key]
}
func (this *LFUCache) Put(key int, value int) {
if _, ok := this.val[key]; ok {
this.val[key] = value
this.touch(key)
return
}
if len(this.val) == this.cap {
head := this.groups[this.minf]
old := head.next
old.prev.next, old.next.prev = old.next, old.prev
if head.next == head {
delete(this.groups, this.minf)
}
delete(this.val, old.key)
delete(this.cnt, old.key)
delete(this.node, old.key)
}
this.val[key] = value
this.cnt[key] = 1
n := &lfuNode{key: key}
this.node[key] = n
this.appendTo(1, n)
this.minf = 1
}class LFUCache {
constructor(capacity) {
this.cap = capacity;
this.val = new Map();
this.cnt = new Map();
this.groups = new Map();
this.minf = 0;
}
touch(key) {
const f = this.cnt.get(key);
this.groups.get(f).delete(key);
if (this.groups.get(f).size === 0) {
this.groups.delete(f);
if (this.minf === f) {
this.minf = f + 1;
}
}
this.cnt.set(key, f + 1);
if (!this.groups.has(f + 1)) {
this.groups.set(f + 1, new Set());
}
this.groups.get(f + 1).add(key);
}
get(key) {
if (!this.val.has(key)) {
return -1;
}
this.touch(key);
return this.val.get(key);
}
put(key, value) {
if (this.val.has(key)) {
this.val.set(key, value);
this.touch(key);
return;
}
if (this.val.size === this.cap) {
const g = this.groups.get(this.minf);
const old = g.values().next().value;
g.delete(old);
if (g.size === 0) {
this.groups.delete(this.minf);
}
this.val.delete(old);
this.cnt.delete(old);
}
this.val.set(key, value);
this.cnt.set(key, 1);
if (!this.groups.has(1)) {
this.groups.set(1, new Set());
}
this.groups.get(1).add(key);
this.minf = 1;
}
}class LFUCache {
cap: number;
val: Map<number, number>;
cnt: Map<number, number>;
groups: Map<number, Set<number>>;
minf: number;
constructor(capacity: number) {
this.cap = capacity;
this.val = new Map();
this.cnt = new Map();
this.groups = new Map();
this.minf = 0;
}
touch(key: number): void {
const f = this.cnt.get(key)!;
this.groups.get(f)!.delete(key);
if (this.groups.get(f)!.size === 0) {
this.groups.delete(f);
if (this.minf === f) {
this.minf = f + 1;
}
}
this.cnt.set(key, f + 1);
if (!this.groups.has(f + 1)) {
this.groups.set(f + 1, new Set());
}
this.groups.get(f + 1)!.add(key);
}
get(key: number): number {
if (!this.val.has(key)) {
return -1;
}
this.touch(key);
return this.val.get(key)!;
}
put(key: number, value: number): void {
if (this.val.has(key)) {
this.val.set(key, value);
this.touch(key);
return;
}
if (this.val.size === this.cap) {
const g = this.groups.get(this.minf)!;
const old = g.values().next().value as number;
g.delete(old);
if (g.size === 0) {
this.groups.delete(this.minf);
}
this.val.delete(old);
this.cnt.delete(old);
}
this.val.set(key, value);
this.cnt.set(key, 1);
if (!this.groups.has(1)) {
this.groups.set(1, new Set());
}
this.groups.get(1)!.add(key);
this.minf = 1;
}
}其他解法
频率分组链表做到严格 O(1)，但指针和最小频率的维护容易出错；小根堆把“频率最低、最久未用”交给堆排序，代码简单但慢一个 log。
解法 2：哈希表 + 小根堆（懒删除） 时间 O(log m)，空间 O(m)
用哈希表记录每个键的值、使用频率和最近访问时间戳。每次访问都把（频率, 时间戳, 键）压入小根堆，不删除旧记录。需要淘汰时不断弹出堆顶，只有与键当前频率和时间戳都一致的记录才有效，删除这个键。m 为操作次数。
不需要维护复杂的链表和最小频率，思路直接，容易写对。每次操作是对数级，堆里会堆积过期记录，空间与操作次数相关。
class LFUCache:
def __init__(self, capacity: int = 2):
self.cap = capacity
self.val = {}
self.freq = {}
self.tick = {} # 键最近一次被访问的时间戳
self.clock = 0
self.heap = [] # (频率, 时间戳, 键)，旧记录懒删除
def _touch(self, key: int, f: int) -> None:
self.clock += 1
self.freq[key] = f
self.tick[key] = self.clock
heapq.heappush(self.heap, (f, self.clock, key))
def get(self, key: int) -> int:
if key not in self.val:
return -1
self._touch(key, self.freq[key] + 1)
return self.val[key]
def put(self, key: int, value: int) -> None:
if key in self.val:
self.val[key] = value
self._touch(key, self.freq[key] + 1)
return
if len(self.val) == self.cap:
while True:
f, t, k = heapq.heappop(self.heap)
# 只有与键当前状态一致的记录才有效
if k in self.val and self.freq[k] == f and self.tick[k] == t:
del self.val[k], self.freq[k], self.tick[k]
break
self.val[key] = value
self._touch(key, 1)class LFUCache {
private int cap, clock = 0;
private Map<Integer, Integer> val = new HashMap<>(), freq = new HashMap<>(), tick = new HashMap<>();
// 小根堆元素：{频率, 时间戳, 键}，旧记录懒删除
private PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1]));
public LFUCache(int capacity) {
cap = capacity;
}
private void touch(int key, int f) {
clock++;
freq.put(key, f);
tick.put(key, clock);
heap.offer(new int[]{f, clock, key});
}
public int get(int key) {
if (!val.containsKey(key)) return -1;
touch(key, freq.get(key) + 1);
return val.get(key);
}
public void put(int key, int value) {
if (val.containsKey(key)) {
val.put(key, value);
touch(key, freq.get(key) + 1);
return;
}
if (val.size() == cap) {
while (true) {
int[] e = heap.poll();
int k = e[2];
if (val.containsKey(k) && freq.get(k) == e[0] && tick.get(k) == e[1]) {
val.remove(k);
freq.remove(k);
tick.remove(k);
break;
}
}
}
val.put(key, value);
touch(key, 1);
}
}class LFUCache {
public:
int cap, clock = 0;
unordered_map<int, int> val, freq, tick;
// 小根堆元素：(频率, 时间戳, 键)，旧记录懒删除
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> heap;
LFUCache(int capacity) : cap(capacity) {}
void touch(int key, int f) {
clock++;
freq[key] = f;
tick[key] = clock;
heap.emplace(f, clock, key);
}
int get(int key) {
if (!val.count(key)) return -1;
touch(key, freq[key] + 1);
return val[key];
}
void put(int key, int value) {
if (val.count(key)) {
val[key] = value;
touch(key, freq[key] + 1);
return;
}
if ((int)val.size() == cap) {
while (true) {
auto [f, t, k] = heap.top();
heap.pop();
if (val.count(k) && freq[k] == f && tick[k] == t) {
val.erase(k);
freq.erase(k);
tick.erase(k);
break;
}
}
}
val[key] = value;
touch(key, 1);
}
};type lfuEntry struct{ f, t, key int }
type lfuHeap []lfuEntry
func (h lfuHeap) Len() int { return len(h) }
func (h lfuHeap) Less(i, j int) bool {
if h[i].f != h[j].f {
return h[i].f < h[j].f
}
return h[i].t < h[j].t
}
func (h lfuHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *lfuHeap) Push(x interface{}) { *h = append(*h, x.(lfuEntry)) }
func (h *lfuHeap) Pop() interface{} {
old := *h
x := old[len(old)-1]
*h = old[:len(old)-1]
return x
}
type LFUCache struct {
cap, clock int
val, freq, tick map[int]int
h *lfuHeap
}
func Constructor(capacity int) LFUCache {
return LFUCache{cap: capacity, val: map[int]int{}, freq: map[int]int{}, tick: map[int]int{}, h: &lfuHeap{}}
}
func (this *LFUCache) touch(key, f int) {
this.clock++
this.freq[key] = f
this.tick[key] = this.clock
heap.Push(this.h, lfuEntry{f, this.clock, key})
}
func (this *LFUCache) Get(key int) int {
v, ok := this.val[key]
if !ok {
return -1
}
this.touch(key, this.freq[key]+1)
return v
}
func (this *LFUCache) Put(key int, value int) {
if _, ok := this.val[key]; ok {
this.val[key] = value
this.touch(key, this.freq[key]+1)
return
}
if len(this.val) == this.cap {
for {
e := heap.Pop(this.h).(lfuEntry)
if _, ok := this.val[e.key]; ok && this.freq[e.key] == e.f && this.tick[e.key] == e.t {
delete(this.val, e.key)
delete(this.freq, e.key)
delete(this.tick, e.key)
break
}
}
}
this.val[key] = value
this.touch(key, 1)
}class LFUCache {
constructor(capacity) {
this.cap = capacity;
this.val = new Map();
this.freq = new Map();
this.tick = new Map();
this.clock = 0;
this.heap = []; // 小根堆元素：[频率, 时间戳, 键]，旧记录懒删除
}
less(a, b) {
return a[0] !== b[0] ? a[0] < b[0] : a[1] < b[1];
}
push(e) {
const h = this.heap;
h.push(e);
let i = h.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (!this.less(h[i], h[p])) break;
[h[i], h[p]] = [h[p], h[i]];
i = p;
}
}
pop() {
const h = this.heap;
const top = h[0], last = h.pop();
if (h.length) {
h[0] = last;
let i = 0;
while (true) {
let m = i;
const l = 2 * i + 1, r = l + 1;
if (l < h.length && this.less(h[l], h[m])) m = l;
if (r < h.length && this.less(h[r], h[m])) m = r;
if (m === i) break;
[h[i], h[m]] = [h[m], h[i]];
i = m;
}
}
return top;
}
touch(key, f) {
this.clock++;
this.freq.set(key, f);
this.tick.set(key, this.clock);
this.push([f, this.clock, key]);
}
get(key) {
if (!this.val.has(key)) return -1;
this.touch(key, this.freq.get(key) + 1);
return this.val.get(key);
}
put(key, value) {
if (this.val.has(key)) {
this.val.set(key, value);
this.touch(key, this.freq.get(key) + 1);
return;
}
if (this.val.size === this.cap) {
while (true) {
const [f, t, k] = this.pop();
if (this.val.has(k) && this.freq.get(k) === f && this.tick.get(k) === t) {
this.val.delete(k);
this.freq.delete(k);
this.tick.delete(k);
break;
}
}
}
this.val.set(key, value);
this.touch(key, 1);
}
}class LFUCache {
cap: number;
val: Map<number, number>;
freq: Map<number, number>;
tick: Map<number, number>;
clock: number;
heap: number[][];
constructor(capacity: number) {
this.cap = capacity;
this.val = new Map();
this.freq = new Map();
this.tick = new Map();
this.clock = 0;
this.heap = []; // 小根堆元素：[频率, 时间戳, 键]，旧记录懒删除
}
less(a: number[], b: number[]): boolean {
return a[0] !== b[0] ? a[0] < b[0] : a[1] < b[1];
}
push(e: number[]): void {
const h = this.heap;
h.push(e);
let i = h.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (!this.less(h[i], h[p])) break;
[h[i], h[p]] = [h[p], h[i]];
i = p;
}
}
pop(): number[] {
const h = this.heap;
const top = h[0], last = h.pop()!;
if (h.length) {
h[0] = last;
let i = 0;
while (true) {
let m = i;
const l = 2 * i + 1, r = l + 1;
if (l < h.length && this.less(h[l], h[m])) m = l;
if (r < h.length && this.less(h[r], h[m])) m = r;
if (m === i) break;
[h[i], h[m]] = [h[m], h[i]];
i = m;
}
}
return top;
}
touch(key: number, f: number): void {
this.clock++;
this.freq.set(key, f);
this.tick.set(key, this.clock);
this.push([f, this.clock, key]);
}
get(key: number): number {
if (!this.val.has(key)) return -1;
this.touch(key, this.freq.get(key)! + 1);
return this.val.get(key)!;
}
put(key: number, value: number): void {
if (this.val.has(key)) {
this.val.set(key, value);
this.touch(key, this.freq.get(key)! + 1);
return;
}
if (this.val.size === this.cap) {
while (true) {
const [f, t, k] = this.pop();
if (this.val.has(k) && this.freq.get(k) === f && this.tick.get(k) === t) {
this.val.delete(k);
this.freq.delete(k);
this.tick.delete(k);
break;
}
}
}
this.val.set(key, value);
this.touch(key, 1);
}
}