Links

0460. LFU 缓存

题目地址(460. LFU缓存)

题目描述

请你为 最不经常使用(LFU)缓存算法设计并实现数据结构。它应该支持以下操作:get 和 put。
get(key) - 如果键存在于缓存中,则获取键的值(总是正数),否则返回 -1。
put(key, value) - 如果键已存在,则变更其值;如果键不存在,请插入键值对。当缓存达到其容量时,则应该在插入新项之前,使最不经常使用的项无效。在此问题中,当存在平局(即两个或更多个键具有相同使用频率)时,应该去除最久未使用的键。
「项的使用次数」就是自插入该项以来对其调用 get 和 put 函数的次数之和。使用次数会在对应项被移除后置为 0 。
进阶:
你是否可以在 O(1) 时间复杂度内执行两项操作?
示例:
LFUCache cache = new LFUCache( 2 /* capacity (缓存容量) */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 去除 key 2
cache.get(2); // 返回 -1 (未找到key 2)
cache.get(3); // 返回 3
cache.put(4, 4); // 去除 key 1
cache.get(1); // 返回 -1 (未找到 key 1)
cache.get(3); // 返回 3
cache.get(4); // 返回 4

前置知识

  • 链表
  • HashMap

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节

思路

本题已被收录到我的新书中,敬请期待~
LFU(Least frequently used) 但内存容量满的情况下,有新的数据进来,需要更多空间的时候,就需要删除被访问频率最少的元素。
举个例子,比如说 cache 容量是 3,按顺序依次放入 1,2,1,2,1,3, cache 已存满 3 个元素 (1,2,3), 这时如果想放入一个新的元素 4 的时候,就需要腾出一个元素空间。 用 LFU,这里就淘汰 3, 因为 3 的次数只出现依次, 1 和 2 出现的次数都比 3 多。
题中 getput 都是 O(1)的时间复杂度,那么删除和增加都是O(1),可以想到用双链表,和HashMap,用一个HashMap, nodeMap, 保存当前key,和 node{key, value, frequent}的映射。 这样get(key)的操作就是O(1). 如果要删除一个元素,那么就需要另一个HashMap,freqMap,保存元素出现次数(frequent)和双链表(DoublyLinkedlist) 映射, 这里双链表存的是 frequent 相同的元素。每次getput的时候,frequent+1,然后把node插入到双链表的head node, head.next=node 每次删除freqent最小的双链表的tail node, tail.prev
用给的例子举例说明:
1. put(1, 1),
- 首先查找 nodeMap 中有没有 key=1 对应的 value,
没有就新建 node(key, value, freq) -> node1(1, 1, 1), 插入 nodeMap,{[1, node1]}
- 查找 freqMap 中有没有 freq=1 对应的 value,
没有就新建 doublylinkedlist(head, tail), 把 node1 插入 doublylinkedlist head->next = node1.
如下图,
460.lfu-cache-1
2. put(2, 2),
- 首先查找 nodeMap 中有没有 key=2 对应的 value,
没有就新建 node(key, value, freq) -> node2(2, 2, 1), 插入 nodeMap,{[1, node1], [2, node2]}
- 查找 freqMap 中有没有 freq=1 对应的 value,
没有就新建 doublylinkedlist(head, tail), 把 node2 插入 doublylinkedlist head->next = node2.
如下图,
460.lfu-cache-2
3. get(1),
- 首先查找 nodeMap 中有没有 key=1 对应的 value,nodeMap:{[1, node1], [2, node2]},
找到 node1,把 node1 freq+1 -> node1(1,1,2)
- 更新 freqMap,删除 freq=1,node1
- 更新 freqMap,插入 freq=2,node1
如下图,
460.lfu-cache-3
4. put(3, 3),
- 判断 cache 的 capacity,已满,需要淘汰使用次数最少的元素,找到最小的 freq=1,删除双链表 tail node.prev
如果 tailnode.prev != null, 删除。然后从 nodeMap 中删除对应的 key。
- 首先查找 nodeMap 中有没有 key=3 对应的 value,
没有就新建 node(key, value, freq) -> node3(3, 3, 1), 插入 nodeMap,{[1, node1], [3, node3]}
- 查找 freqMap 中有没有 freq=1 对应的 value,
没有就新建 doublylinkedlist(head, tail), 把 node3 插入 doublylinkedlist head->next = node3.
如下图,
460.lfu-cache-4
5. get(2)
- 查找 nodeMap,如果没有对应的 key 的 value,返回 -1。
6. get(3)
- 首先查找 nodeMap 中有没有 key=3 对应的 value,nodeMap:{[1, node1], [3, node3]},
找到 node3,把 node3 freq+1 -> node3(3,3,2)
- 更新 freqMap,删除 freq=1,node3
- 更新 freqMap,插入 freq=2,node3
如下图,
460.lfu-cache-5
7. put(4, 4),
- 判断 cache 的 capacity,已满,需要淘汰使用次数最少的元素,找到最小的 freq=1,删除双链表 tail node.prev
如果 tailnode.prev != null, 删除。然后从 nodeMap 中删除对应的 key。
- 首先查找 nodeMap 中有没有 key=4 对应的 value,
没有就新建 node(key, value, freq) -> node4(4, 4, 1), 插入 nodeMap,{[4, node4], [3, node3]}
- 查找 freqMap 中有没有 freq=1 对应的 value,
没有就新建 doublylinkedlist(head, tail), 把 node4 插入 doublylinkedlist head->next = node4.
如下图,
460.lfu-cache-6
8. get(1)
- 查找 nodeMap,如果没有对应的 key 的 value,返回 -1。
9. get(3)
- 首先查找 nodeMap 中有没有 key=3 对应的 value,nodeMap:{[4, node4], [3, node3]},
找到 node3,把 node3 freq+1 -> node3(3,3,3)
- 更新 freqMap,删除 freq=2,node3
- 更新 freqMap,插入 freq=3,node3
如下图,
460.lfu-cache-7
10. get(4)
- 首先查找 nodeMap 中有没有 key=4 对应的 value,nodeMap:{[4, node4], [3, node3]},
找到 node4,把 node4 freq+1 -> node4(4,4,2)
- 更新 freqMap,删除 freq=1,node4
- 更新 freqMap,插入 freq=2,node4
如下图,
460.lfu-cache-8

关键点分析

用两个Map分别保存 nodeMap {key, node}freqMap{frequent, DoublyLinkedList}。 实现getput操作都是O(1)的时间复杂度。
可以用 Java 自带的一些数据结构,比如 HashLinkedHashSet,这样就不需要自己自建 Node,DoublelyLinkedList。 可以很大程度的缩减代码量。

代码(Java code)

public class LC460LFUCache {
class Node {
int key, val, freq;
Node prev, next;
Node(int key, int val) {
this.key = key;
this.val = val;
freq = 1;
}
}
class DoubleLinkedList {
private Node head;
private Node tail;
private int size;
DoubleLinkedList() {
head = new Node(0, 0);
tail = new Node(0, 0);
head.next = tail;
tail.prev = head;
}
void add(Node node) {
head.next.prev = node;
node.next = head.next;
node.prev = head;
head.next = node;
size++;
}
void remove(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
size--;
}
// always remove last node if last node exists
Node removeLast() {
if (size > 0) {
Node node = tail.prev;
remove(node);
return node;
} else return null;
}
}
// cache capacity
private int capacity;
// min frequent
private int minFreq;
Map<Integer, Node> nodeMap;
Map<Integer, DoubleLinkedList> freqMap;
public LC460LFUCache(int capacity) {
this.minFreq = 0;
this.capacity = capacity;
nodeMap = new HashMap<>();
freqMap = new HashMap<>();
}
public int get(int key) {
Node node = nodeMap.get(key);
if (node == null) return -1;
update(node);
return node.val;
}
public void put(int key, int value) {
if (capacity == 0) return;
Node node;
if (nodeMap.containsKey(key)) {
node = nodeMap.get(key);
node.val = value;
update(node);
} else {
node = new Node(key, value);
nodeMap.put(key, node);
if (nodeMap.size() == capacity) {
DoubleLinkedList lastList = freqMap.get(minFreq);
nodeMap.remove(lastList.removeLast().key);
}
minFreq = 1;
DoubleLinkedList newList = freqMap.getOrDefault(node.freq, new DoubleLinkedList());
newList.add(node);
freqMap.put(node.freq, newList);
}
}
private void update(Node node) {
DoubleLinkedList oldList = freqMap.get(node.freq);
oldList.remove(node);
if (node.freq == minFreq && oldList.size == 0) minFreq++;
node.freq++;
DoubleLinkedList newList = freqMap.getOrDefault(node.freq, new DoubleLinkedList());
newList.add(node);
freqMap.put(node.freq, newList);
}
}

参考(References)