0460. LFU 缓存
题目地址(460. LFU缓存)
题目描述
1
请你为 最不经常使用（LFU）缓存算法设计并实现数据结构。它应该支持以下操作：get 和 put。
2
3
get(key) - 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。
4
put(key, value) - 如果键已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量时，则应该在插入新项之前，使最不经常使用的项无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除最久未使用的键。
5
「项的使用次数」就是自插入该项以来对其调用 get 和 put 函数的次数之和。使用次数会在对应项被移除后置为 0 。
6
7
8
9
进阶：
10
你是否可以在 O(1) 时间复杂度内执行两项操作？
11
12
13
14
示例：
15
16
LFUCache cache = new LFUCache( 2 /* capacity (缓存容量) */ );
17
18
cache.put(1, 1);
19
cache.put(2, 2);
20
cache.get(1); // 返回 1
21
cache.put(3, 3); // 去除 key 2
22
cache.get(2); // 返回 -1 (未找到key 2)
23
cache.get(3); // 返回 3
24
cache.put(4, 4); // 去除 key 1
25
cache.get(1); // 返回 -1 (未找到 key 1)
26
cache.get(3); // 返回 3
27
cache.get(4); // 返回 4
Copied!
前置知识
- 链表
- HashMap
公司
- 阿里
- 腾讯
- 百度
- 字节
思路
本题已被收录到我的新书中，敬请期待～举个例子，比如说 cache 容量是 3，按顺序依次放入
1，2，1，2，1，3， cache 已存满 3 个元素 (1，2，3)， 这时如果想放入一个新的元素 4 的时候，就需要腾出一个元素空间。 用 LFU，这里就淘汰 3， 因为 3 的次数只出现依次， 1 和 2 出现的次数都比 3 多。题中
get 和 put 都是 O(1)的时间复杂度，那么删除和增加都是O(1)，可以想到用双链表，和HashMap，用一个HashMap, nodeMap, 保存当前key，和 node{key, value, frequent}的映射。 这样get(key)的操作就是O(1). 如果要删除一个元素，那么就需要另一个HashMap，freqMap，保存元素出现次数（frequent）和双链表（DoublyLinkedlist） 映射， 这里双链表存的是 frequent 相同的元素。每次get或put的时候，frequent+1，然后把node插入到双链表的head node, head.next=node 每次删除freqent最小的双链表的tail node, tail.prev。用给的例子举例说明：
1
1. put(1, 1),
2
- 首先查找 nodeMap 中有没有 key=1 对应的 value，
3
没有就新建 node(key, value, freq) -> node1(1, 1, 1), 插入 nodeMap，{[1, node1]}
4
- 查找 freqMap 中有没有 freq=1 对应的 value，
5
没有就新建 doublylinkedlist(head, tail), 把 node1 插入 doublylinkedlist head->next = node1.
6
如下图，
Copied!
460.lfu-cache-1
1
2. put(2, 2),
2
- 首先查找 nodeMap 中有没有 key=2 对应的 value，
3
没有就新建 node(key, value, freq) -> node2(2, 2, 1), 插入 nodeMap，{[1, node1], [2, node2]}
4
- 查找 freqMap 中有没有 freq=1 对应的 value，
5
没有就新建 doublylinkedlist(head, tail), 把 node2 插入 doublylinkedlist head->next = node2.
6
如下图，
Copied!
460.lfu-cache-2
1
3. get(1),
2
- 首先查找 nodeMap 中有没有 key=1 对应的 value，nodeMap:{[1, node1], [2, node2]},
3
找到 node1，把 node1 freq+1 -> node1(1,1,2)
4
- 更新 freqMap，删除 freq=1，node1
5
- 更新 freqMap，插入 freq=2，node1
6
如下图，
Copied!
460.lfu-cache-3
1
4. put(3, 3),
2
- 判断 cache 的 capacity，已满，需要淘汰使用次数最少的元素，找到最小的 freq=1，删除双链表 tail node.prev
3
如果 tailnode.prev != null, 删除。然后从 nodeMap 中删除对应的 key。
4
- 首先查找 nodeMap 中有没有 key=3 对应的 value，
5
没有就新建 node(key, value, freq) -> node3(3, 3, 1), 插入 nodeMap，{[1, node1], [3, node3]}
6
- 查找 freqMap 中有没有 freq=1 对应的 value，
7
没有就新建 doublylinkedlist(head, tail), 把 node3 插入 doublylinkedlist head->next = node3.
8
如下图，
Copied!
460.lfu-cache-4
1
5. get(2)
2
- 查找 nodeMap，如果没有对应的 key 的 value，返回 -1。
3
4
6. get(3)
5
- 首先查找 nodeMap 中有没有 key=3 对应的 value，nodeMap:{[1, node1], [3, node3]},
6
找到 node3，把 node3 freq+1 -> node3(3,3,2)
7
- 更新 freqMap，删除 freq=1，node3
8
- 更新 freqMap，插入 freq=2，node3
9
如下图，
Copied!
460.lfu-cache-5
1
7. put(4, 4),
2
- 判断 cache 的 capacity，已满，需要淘汰使用次数最少的元素，找到最小的 freq=1，删除双链表 tail node.prev
3
如果 tailnode.prev != null, 删除。然后从 nodeMap 中删除对应的 key。
4
- 首先查找 nodeMap 中有没有 key=4 对应的 value，
5
没有就新建 node(key, value, freq) -> node4(4, 4, 1), 插入 nodeMap，{[4, node4], [3, node3]}
6
- 查找 freqMap 中有没有 freq=1 对应的 value，
7
没有就新建 doublylinkedlist(head, tail), 把 node4 插入 doublylinkedlist head->next = node4.
8
如下图，
Copied!
460.lfu-cache-6
1
8. get(1)
2
- 查找 nodeMap，如果没有对应的 key 的 value，返回 -1。
3
4
9. get(3)
5
- 首先查找 nodeMap 中有没有 key=3 对应的 value，nodeMap:{[4, node4], [3, node3]},
6
找到 node3，把 node3 freq+1 -> node3(3,3,3)
7
- 更新 freqMap，删除 freq=2，node3
8
- 更新 freqMap，插入 freq=3，node3
9
如下图，
Copied!
460.lfu-cache-7
1
10. get(4)
2
- 首先查找 nodeMap 中有没有 key=4 对应的 value，nodeMap:{[4, node4], [3, node3]},
3
找到 node4，把 node4 freq+1 -> node4(4,4,2)
4
- 更新 freqMap，删除 freq=1，node4
5
- 更新 freqMap，插入 freq=2，node4
6
如下图，
Copied!
460.lfu-cache-8
关键点分析
用两个
Map分别保存 nodeMap {key, node} 和 freqMap{frequent, DoublyLinkedList}。 实现get 和 put操作都是O(1)的时间复杂度。可以用 Java 自带的一些数据结构，比如 HashLinkedHashSet，这样就不需要自己自建 Node，DoublelyLinkedList。 可以很大程度的缩减代码量。
代码（Java code）
1
public class LC460LFUCache {
2
class Node {
3
int key, val, freq;
4
Node prev, next;
5
6
Node(int key, int val) {
7
this.key = key;
8
this.val = val;
9
freq = 1;
10
}
11
}
12
13
class DoubleLinkedList {
14
private Node head;
15
private Node tail;
16
private int size;
17
18
DoubleLinkedList() {
19
head = new Node(0, 0);
20
tail = new Node(0, 0);
21
head.next = tail;
22
tail.prev = head;
23
}
24
25
void add(Node node) {
26
head.next.prev = node;
27
node.next = head.next;
28
node.prev = head;
29
head.next = node;
30
size++;
31
}
32
33
void remove(Node node) {
34
node.prev.next = node.next;
35
node.next.prev = node.prev;
36
size--;
37
}
38
39
// always remove last node if last node exists
40
Node removeLast() {
41
if (size > 0) {
42
Node node = tail.prev;
43
remove(node);
44
return node;
45
} else return null;
46
}
47
}
48
49
// cache capacity
50
private int capacity;
51
// min frequent
52
private int minFreq;
53
Map<Integer, Node> nodeMap;
54
Map<Integer, DoubleLinkedList> freqMap;
55
public LC460LFUCache(int capacity) {
56
this.minFreq = 0;
57
this.capacity = capacity;
58
nodeMap = new HashMap<>();
59
freqMap = new HashMap<>();
60
}
61
62
public int get(int key) {
63
Node node = nodeMap.get(key);
64
if (node == null) return -1;
65
update(node);
66
return node.val;
67
}
68
69
public void put(int key, int value) {
70
if (capacity == 0) return;
71
Node node;
72
if (nodeMap.containsKey(key)) {
73
node = nodeMap.get(key);
74
node.val = value;
75
update(node);
76
} else {
77
node = new Node(key, value);
78
nodeMap.put(key, node);
79
if (nodeMap.size() == capacity) {
80
DoubleLinkedList lastList = freqMap.get(minFreq);
81
nodeMap.remove(lastList.removeLast().key);
82
}
83
minFreq = 1;
84
DoubleLinkedList newList = freqMap.getOrDefault(node.freq, new DoubleLinkedList());
85
newList.add(node);
86
freqMap.put(node.freq, newList);
87
}
88
}
89
90
private void update(Node node) {
91
DoubleLinkedList oldList = freqMap.get(node.freq);
92
oldList.remove(node);
93
if (node.freq == minFreq && oldList.size == 0) minFreq++;
94
node.freq++;
95
DoubleLinkedList newList = freqMap.getOrDefault(node.freq, new DoubleLinkedList());
96
newList.add(node);
97
freqMap.put(node.freq, newList);
98
}
99
}
Copied!
参考（References）
- 2.[Leetcode discussion mylzsd](https://leetcode.com/problems/lfu-cache/discuss/94547/Java-O(1)-Solution-Using-Two-HashMap-and-One-DoubleLinkedList)
- 3.[Leetcode discussion aaaeeeo](https://leetcode.com/problems/lfu-cache/discuss/94547/Java-O(1)-Solution-Using-Two-HashMap-and-One-DoubleLinkedList)
最近更新 1yr ago