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
提示：
0 <= capacity <= 1040 <= key <= 1050 <= value <= 1092 * 105 次 get 和 put 方法原站题解
cpp 解法, 执行用时: 572 ms, 内存消耗: 176.2 MB, 提交时间: 2023-09-25 07:32:00
// 缓存的节点信息
struct Node {
int key, val, freq;
Node(int _key,int _val,int _freq): key(_key), val(_val), freq(_freq){}
};
class LFUCache {
int minfreq, capacity;
unordered_map<int, list<Node>::iterator> key_table;
unordered_map<int, list<Node>> freq_table;
public:
LFUCache(int _capacity) {
minfreq = 0;
capacity = _capacity;
key_table.clear();
freq_table.clear();
}
int get(int key) {
if (capacity == 0) return -1;
auto it = key_table.find(key);
if (it == key_table.end()) return -1;
list<Node>::iterator node = it -> second;
int val = node -> val, freq = node -> freq;
freq_table[freq].erase(node);
// 如果当前链表为空，我们需要在哈希表中删除，且更新minFreq
if (freq_table[freq].size() == 0) {
freq_table.erase(freq);
if (minfreq == freq) minfreq += 1;
}
// 插入到 freq + 1 中
freq_table[freq + 1].push_front(Node(key, val, freq + 1));
key_table[key] = freq_table[freq + 1].begin();
return val;
}
void put(int key, int value) {
if (capacity == 0) return;
auto it = key_table.find(key);
if (it == key_table.end()) {
// 缓存已满，需要进行删除操作
if (key_table.size() == capacity) {
// 通过 minFreq 拿到 freq_table[minFreq] 链表的末尾节点
auto it2 = freq_table[minfreq].back();
key_table.erase(it2.key);
freq_table[minfreq].pop_back();
if (freq_table[minfreq].size() == 0) {
freq_table.erase(minfreq);
}
}
freq_table[1].push_front(Node(key, value, 1));
key_table[key] = freq_table[1].begin();
minfreq = 1;
} else {
// 与 get 操作基本一致，除了需要更新缓存的值
list<Node>::iterator node = it -> second;
int freq = node -> freq;
freq_table[freq].erase(node);
if (freq_table[freq].size() == 0) {
freq_table.erase(freq);
if (minfreq == freq) minfreq += 1;
}
freq_table[freq + 1].push_front(Node(key, value, freq + 1));
key_table[key] = freq_table[freq + 1].begin();
}
}
};
/**
* Your LFUCache object will be instantiated and called as such:
* LFUCache* obj = new LFUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/
cpp 解法, 执行用时: 464 ms, 内存消耗: 178.6 MB, 提交时间: 2023-09-25 07:31:37
struct Node {
int cnt, time, key, value;
Node(int _cnt, int _time, int _key, int _value):cnt(_cnt), time(_time), key(_key), value(_value){}
bool operator < (const Node& rhs) const {
return cnt == rhs.cnt ? time < rhs.time : cnt < rhs.cnt;
}
};
class LFUCache {
// 缓存容量，时间戳
int capacity, time;
unordered_map<int, Node> key_table;
set<Node> S;
public:
LFUCache(int _capacity) {
capacity = _capacity;
time = 0;
key_table.clear();
S.clear();
}
int get(int key) {
if (capacity == 0) return -1;
auto it = key_table.find(key);
// 如果哈希表中没有键 key，返回 -1
if (it == key_table.end()) return -1;
// 从哈希表中得到旧的缓存
Node cache = it -> second;
// 从平衡二叉树中删除旧的缓存
S.erase(cache);
// 将旧缓存更新
cache.cnt += 1;
cache.time = ++time;
// 将新缓存重新放入哈希表和平衡二叉树中
S.insert(cache);
it -> second = cache;
return cache.value;
}
void put(int key, int value) {
if (capacity == 0) return;
auto it = key_table.find(key);
if (it == key_table.end()) {
// 如果到达缓存容量上限
if (key_table.size() == capacity) {
// 从哈希表和平衡二叉树中删除最近最少使用的缓存
key_table.erase(S.begin() -> key);
S.erase(S.begin());
}
// 创建新的缓存
Node cache = Node(1, ++time, key, value);
// 将新缓存放入哈希表和平衡二叉树中
key_table.insert(make_pair(key, cache));
S.insert(cache);
}
else {
// 这里和 get() 函数类似
Node cache = it -> second;
S.erase(cache);
cache.cnt += 1;
cache.time = ++time;
cache.value = value;
S.insert(cache);
it -> second = cache;
}
}
};
/**
* Your LFUCache object will be instantiated and called as such:
* LFUCache* obj = new LFUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/
golang 解法, 执行用时: 444 ms, 内存消耗: 73 MB, 提交时间: 2023-09-11 11:13:00
type LFUCache struct {
cache map[int]*Node
freq map[int]*DoubleList
ncap, size, minFreq int
}
func Constructor(capacity int) LFUCache {
return LFUCache {
cache: make(map[int]*Node),
freq: make(map[int]*DoubleList),
ncap: capacity,
}
}
func (this *LFUCache) Get(key int) int {
if node, ok := this.cache[key]; ok {
this.IncFreq(node)
return node.val
}
return -1
}
func (this *LFUCache) Put(key, value int) {
if this.ncap == 0 {
return
}
if node, ok := this.cache[key]; ok {
node.val = value
this.IncFreq(node)
} else {
if this.size >= this.ncap {
node := this.freq[this.minFreq].RemoveLast()
delete(this.cache, node.key)
this.size--
}
x := &Node{key: key, val: value, freq: 1}
this.cache[key] = x
if this.freq[1] == nil {
this.freq[1] = CreateDL()
}
this.freq[1].AddFirst(x)
this.minFreq = 1
this.size++
}
}
func (this *LFUCache) IncFreq(node *Node) {
_freq := node.freq
this.freq[_freq].Remove(node)
if this.minFreq == _freq && this.freq[_freq].IsEmpty() {
this.minFreq++
delete(this.freq, _freq)
}
node.freq++
if this.freq[node.freq] == nil {
this.freq[node.freq] = CreateDL()
}
this.freq[node.freq].AddFirst(node)
}
type DoubleList struct {
head, tail *Node
}
type Node struct {
prev, next *Node
key, val, freq int
}
func CreateDL() *DoubleList {
head, tail := &Node{}, &Node{}
head.next, tail.prev = tail, head
return &DoubleList {
head: head,
tail: tail,
}
}
func (this *DoubleList) AddFirst(node *Node) {
node.next = this.head.next
node.prev = this.head
this.head.next.prev = node
this.head.next = node
}
func (this *DoubleList) Remove(node *Node) {
node.prev.next = node.next
node.next.prev = node.prev
node.next = nil
node.prev = nil
}
func (this *DoubleList) RemoveLast() *Node {
if this.IsEmpty() {
return nil
}
last := this.tail.prev
this.Remove(last)
return last
}
func (this *DoubleList) IsEmpty() bool {
return this.head.next == this.tail
}
/**
* Your LFUCache object will be instantiated and called as such:
* obj := Constructor(capacity);
* param_1 := obj.Get(key);
* obj.Put(key,value);
*/
python3 解法, 执行用时: 632 ms, 内存消耗: 77.8 MB, 提交时间: 2023-09-11 11:07:25
class Node:
def __init__(self, key, val, pre=None, nex=None, freq=0):
self.pre = pre
self.nex = nex
self.freq = freq
self.val = val
self.key = key
def insert(self, nex):
nex.pre = self
nex.nex = self.nex
self.nex.pre = nex
self.nex = nex
def create_linked_list():
head = Node(0, 0)
tail = Node(0, 0)
head.nex = tail
tail.pre = head
return (head, tail)
class LFUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.size = 0
self.minFreq = 0
self.freqMap = collections.defaultdict(create_linked_list)
self.keyMap = {}
def delete(self, node):
if node.pre:
node.pre.nex = node.nex
node.nex.pre = node.pre
if node.pre is self.freqMap[node.freq][0] and node.nex is self.freqMap[node.freq][-1]:
self.freqMap.pop(node.freq)
return node.key
def increase(self, node):
node.freq += 1
self.delete(node)
self.freqMap[node.freq][-1].pre.insert(node)
if node.freq == 1:
self.minFreq = 1
elif self.minFreq == node.freq - 1:
head, tail = self.freqMap[node.freq - 1]
if head.nex is tail:
self.minFreq = node.freq
def get(self, key: int) -> int:
if key in self.keyMap:
self.increase(self.keyMap[key])
return self.keyMap[key].val
return -1
def put(self, key: int, value: int) -> None:
if self.capacity != 0:
if key in self.keyMap:
node = self.keyMap[key]
node.val = value
else:
node = Node(key, value)
self.keyMap[key] = node
self.size += 1
if self.size > self.capacity:
self.size -= 1
deleted = self.delete(self.freqMap[self.minFreq][0].nex)
self.keyMap.pop(deleted)
self.increase(node)
# Your LFUCache object will be instantiated and called as such:
# obj = LFUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
java 解法, 执行用时: 56 ms, 内存消耗: 123.8 MB, 提交时间: 2023-09-11 11:06:59
class LFUCache {
int minfreq, capacity;
Map<Integer, Node> keyTable;
Map<Integer, DoublyLinkedList> freqTable;
public LFUCache(int capacity) {
this.minfreq = 0;
this.capacity = capacity;
keyTable = new HashMap<Integer, Node>();
freqTable = new HashMap<Integer, DoublyLinkedList>();
}
public int get(int key) {
if (capacity == 0) {
return -1;
}
if (!keyTable.containsKey(key)) {
return -1;
}
Node node = keyTable.get(key);
int val = node.val, freq = node.freq;
freqTable.get(freq).remove(node);
// 如果当前链表为空，我们需要在哈希表中删除，且更新minFreq
if (freqTable.get(freq).size == 0) {
freqTable.remove(freq);
if (minfreq == freq) {
minfreq += 1;
}
}
// 插入到 freq + 1 中
DoublyLinkedList list = freqTable.getOrDefault(freq + 1, new DoublyLinkedList());
list.addFirst(new Node(key, val, freq + 1));
freqTable.put(freq + 1, list);
keyTable.put(key, freqTable.get(freq + 1).getHead());
return val;
}
public void put(int key, int value) {
if (capacity == 0) {
return;
}
if (!keyTable.containsKey(key)) {
// 缓存已满，需要进行删除操作
if (keyTable.size() == capacity) {
// 通过 minFreq 拿到 freqTable[minFreq] 链表的末尾节点
Node node = freqTable.get(minfreq).getTail();
keyTable.remove(node.key);
freqTable.get(minfreq).remove(node);
if (freqTable.get(minfreq).size == 0) {
freqTable.remove(minfreq);
}
}
DoublyLinkedList list = freqTable.getOrDefault(1, new DoublyLinkedList());
list.addFirst(new Node(key, value, 1));
freqTable.put(1, list);
keyTable.put(key, freqTable.get(1).getHead());
minfreq = 1;
} else {
// 与 get 操作基本一致，除了需要更新缓存的值
Node node = keyTable.get(key);
int freq = node.freq;
freqTable.get(freq).remove(node);
if (freqTable.get(freq).size == 0) {
freqTable.remove(freq);
if (minfreq == freq) {
minfreq += 1;
}
}
DoublyLinkedList list = freqTable.getOrDefault(freq + 1, new DoublyLinkedList());
list.addFirst(new Node(key, value, freq + 1));
freqTable.put(freq + 1, list);
keyTable.put(key, freqTable.get(freq + 1).getHead());
}
}
}
class Node {
int key, val, freq;
Node prev, next;
Node() {
this(-1, -1, 0);
}
Node(int key, int val, int freq) {
this.key = key;
this.val = val;
this.freq = freq;
}
}
class DoublyLinkedList {
Node dummyHead, dummyTail;
int size;
DoublyLinkedList() {
dummyHead = new Node();
dummyTail = new Node();
dummyHead.next = dummyTail;
dummyTail.prev = dummyHead;
size = 0;
}
public void addFirst(Node node) {
Node prevHead = dummyHead.next;
node.prev = dummyHead;
dummyHead.next = node;
node.next = prevHead;
prevHead.prev = node;
size++;
}
public void remove(Node node) {
Node prev = node.prev, next = node.next;
prev.next = next;
next.prev = prev;
size--;
}
public Node getHead() {
return dummyHead.next;
}
public Node getTail() {
return dummyTail.prev;
}
}
/**
* Your LFUCache object will be instantiated and called as such:
* LFUCache obj = new LFUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/
java 解法, 执行用时: 89 ms, 内存消耗: 126 MB, 提交时间: 2023-09-11 11:06:35
class LFUCache {
// 缓存容量，时间戳
int capacity, time;
Map<Integer, Node> key_table;
TreeSet<Node> S;
public LFUCache(int capacity) {
this.capacity = capacity;
this.time = 0;
key_table = new HashMap<Integer, Node>();
S = new TreeSet<Node>();
}
public int get(int key) {
if (capacity == 0) {
return -1;
}
// 如果哈希表中没有键 key，返回 -1
if (!key_table.containsKey(key)) {
return -1;
}
// 从哈希表中得到旧的缓存
Node cache = key_table.get(key);
// 从平衡二叉树中删除旧的缓存
S.remove(cache);
// 将旧缓存更新
cache.cnt += 1;
cache.time = ++time;
// 将新缓存重新放入哈希表和平衡二叉树中
S.add(cache);
key_table.put(key, cache);
return cache.value;
}
public void put(int key, int value) {
if (capacity == 0) {
return;
}
if (!key_table.containsKey(key)) {
// 如果到达缓存容量上限
if (key_table.size() == capacity) {
// 从哈希表和平衡二叉树中删除最近最少使用的缓存
key_table.remove(S.first().key);
S.remove(S.first());
}
// 创建新的缓存
Node cache = new Node(1, ++time, key, value);
// 将新缓存放入哈希表和平衡二叉树中
key_table.put(key, cache);
S.add(cache);
} else {
// 这里和 get() 函数类似
Node cache = key_table.get(key);
S.remove(cache);
cache.cnt += 1;
cache.time = ++time;
cache.value = value;
S.add(cache);
key_table.put(key, cache);
}
}
}
class Node implements Comparable<Node> {
int cnt, time, key, value;
Node(int cnt, int time, int key, int value) {
this.cnt = cnt;
this.time = time;
this.key = key;
this.value = value;
}
public boolean equals(Object anObject) {
if (this == anObject) {
return true;
}
if (anObject instanceof Node) {
Node rhs = (Node) anObject;
return this.cnt == rhs.cnt && this.time == rhs.time;
}
return false;
}
public int compareTo(Node rhs) {
return cnt == rhs.cnt ? time - rhs.time : cnt - rhs.cnt;
}
public int hashCode() {
return cnt * 1000000007 + time;
}
}
/**
* Your LFUCache object will be instantiated and called as such:
* LFUCache obj = new LFUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/
php 解法, 执行用时: 4484 ms, 内存消耗: 143.9 MB, 提交时间: 2023-09-11 11:05:46
class LFUCache
{
public $minFreq;
public $capacity;
public $freqTable;
public $keyTable;
/**
* @param Integer $capacity
*/
function __construct($capacity)
{
$this->minFreq = 0;
$this->capacity = $capacity;
$this->freqTable = [];
$this->keyTable = [];
}
/**
* @param Integer $key
* @return Integer
*/
function get($key)
{
// 每次访问一个已经存在的元素的时候
// 应该先把结点从当前所属的访问次数双链表里删除，
// 然后再添加到它「下一个访问次数」的双向链表的头部；
if ($this->capacity <= 0) return -1;
if (!isset($this->keyTable[$key])) return -1;
$node = $this->keyTable[$key];
$list = $this->freqTable[$node->freq];
if ($node->freq == $this->minFreq && count($list) == 1) $this->minFreq++;
$index = array_search($key, $list);
unset($this->freqTable[$node->freq][$index]);
if (!isset($this->freqTable[$node->freq + 1])) $this->freqTable[$node->freq + 1] = [];
array_unshift($this->freqTable[$node->freq + 1], $key);
$node->freq++;
$this->keyTable[$key] = $node;
return $node->value;
}
/**
* @param Integer $key
* @param Integer $value
* @return null
*/
function put($key, $value)
{
if (isset($this->keyTable[$key])) {
if ($this->capacity <= 0) return -1;
$node = $this->keyTable[$key];
$list = $this->freqTable[$node->freq];
if ($node->freq == $this->minFreq && count($list) == 1) $this->minFreq++;
$index = array_search($key, $list);
unset($this->freqTable[$node->freq][$index]);
if (!isset($this->freqTable[$node->freq + 1])) $this->freqTable[$node->freq + 1] = [];
array_unshift($this->freqTable[$node->freq + 1], $key);
$node->value = $value;
$node->freq++;
$this->keyTable[$key] = $node;
return;
}
// 1、如果满了，先删除访问次数最小的的末尾结点，
// 再删除 map 里对应的 key
if ($this->capacity == count($this->keyTable)) {
if (isset($this->freqTable[$this->minFreq]) && !empty($this->freqTable[$this->minFreq])) {
$tail = array_pop($this->freqTable[$this->minFreq]);
unset($this->keyTable[$tail]);
}
}
// 2、再创建新结点放在访问次数为 1 的双向链表的前面
$node = new LFUNode($key, $value, 1);
$this->keyTable[$key] = $node;
if (!isset($this->freqTable[1])) {
$this->freqTable[1] = [];
}
$this->minFreq = 1;
array_unshift($this->freqTable[1], $key);
}
}
class LFUNode
{
public $key;
public $value;
public $freq;
public function __construct($key, $value, $freq)
{
$this->key = $key;
$this->value = $value;
$this->freq = $freq;
}
}
/**
* Your LFUCache object will be instantiated and called as such:
* $obj = LFUCache($capacity);
* $ret_1 = $obj->get($key);
* $obj->put($key, $value);
*/