460. LFU 缓存

Hard

题目描述

设计并实现最不经常使用（LFU）缓存的数据结构。

实现 LFUCache 类：

LFUCache(int capacity) 用数据结构的容量初始化对象
int get(int key) 如果键存在于缓存中，则获取键的值，否则返回 -1
void put(int key, int value) 如果键已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量时，则应该在插入新项之前，使最不经常使用的项无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除最久未使用的键。

为了确定最不常使用的键，可以为缓存中的每个键维护一个使用计数器。使用计数器最小的键是最不经常使用的键。

当一个键首次插入到缓存中时，它的使用计数器被设置为 1（由于 put 操作）。对缓存中的键执行 get 或 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]

解释：
// 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 是 LFU 键，因为 cnt(2)=1 是最小的，删除键 2
                 // 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 和键 3 的计数相同，但键 1 是 LRU，删除键 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=[4,3], cnt(4)=2, cnt(3)=3

提示：

1 <= capacity <= 10^4
0 <= key <= 10^5
0 <= value <= 10^9
最多调用 2 * 10^5 次 get 和 put 方法

解题思路

LFU 缓存需要同时维护访问频次和访问时间两个维度的信息。核心思路是使用三个哈希表来实现 O(1) 的操作复杂度：

键值存储：key_to_val 存储键值对
频次映射：key_to_freq 记录每个键的访问频次
频次分组：freq_to_keys 将相同频次的键组织在一起，每个频次对应一个双向链表

当需要删除最不常用的键时，找到最小频次 min_freq，从对应的双向链表头部删除最久未使用的键。当访问某个键时，需要将其从当前频次的链表移动到频次+1的链表尾部。

为了维护 min_freq，采用懒惰更新策略：只在某个频次的键列表变空时才更新最小频次。这种设计确保了所有操作都能在 O(1) 时间内完成。

双向链表的使用是关键，它允许我们在 O(1) 时间内插入和删除节点，同时维护访问顺序。

代码实现

class LFUCache {
private:
    int capacity;
    int min_freq;
    unordered_map<int, int> key_to_val;
    unordered_map<int, int> key_to_freq;
    unordered_map<int, list<int>> freq_to_keys;
    unordered_map<int, list<int>::iterator> key_to_iter;
    
public:
    LFUCache(int capacity) : capacity(capacity), min_freq(0) {}
    
    int get(int key) {
        if (key_to_val.find(key) == key_to_val.end()) {
            return -1;
        }
        increaseFreq(key);
        return key_to_val[key];
    }
    
    void put(int key, int value) {
        if (capacity <= 0) return;
        
        if (key_to_val.find(key) != key_to_val.end()) {
            key_to_val[key] = value;
            increaseFreq(key);
            return;
        }
        
        if (key_to_val.size() >= capacity) {
            removeMinFreqKey();
        }
        
        key_to_val[key] = value;
        key_to_freq[key] = 1;
        freq_to_keys[1].push_back(key);
        key_to_iter[key] = prev(freq_to_keys[1].end());
        min_freq = 1;
    }
    
private:
    void increaseFreq(int key) {
        int freq = key_to_freq[key];
        
        freq_to_keys[freq].erase(key_to_iter[key]);
        if (freq_to_keys[freq].empty() && freq == min_freq) {
            min_freq++;
        }
        
        key_to_freq[key] = freq + 1;
        freq_to_keys[freq + 1].push_back(key);
        key_to_iter[key] = prev(freq_to_keys[freq + 1].end());
    }
    
    void removeMinFreqKey() {
        int key = freq_to_keys[min_freq].front();
        freq_to_keys[min_freq].pop_front();
        
        key_to_val.erase(key);
        key_to_freq.erase(key);
        key_to_iter.erase(key);
    }
};

class LFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.min_freq = 0
        self.key_to_val = {}
        self.key_to_freq = {}
        self.freq_to_keys = {}
        
    def get(self, key: int) -> int:
        if key not in self.key_to_val:
            return -1
        self._increase_freq(key)
        return self.key_to_val[key]
    
    def put(self, key: int, value: int) -> None:
        if self.capacity <= 0:
            return
        
        if key in self.key_to_val:
            self.key_to_val[key] = value
            self._increase_freq(key)
            return
        
        if len(self.key_to_val) >= self.capacity:
            self._remove_min_freq_key()
        
        self.key_to_val[key] = value
        self.key_to_freq[key] = 1
        if 1 not in self.freq_to_keys:
            self.freq_to_keys[1] = []
        self.freq_to_keys[1].append(key)
        self.min_freq = 1
    
    def _increase_freq(self, key: int) -> None:
        freq = self.key_to_freq[key]
        self.freq_to_keys[freq].remove(key)
        
        if not self.freq_to_keys[freq] and freq == self.min_freq:
            self.min_freq += 1
        
        self.key_to_freq[key] = freq + 1
        if freq + 1 not in self.freq_to_keys:
            self.freq_to_keys[freq + 1] = []
        self.freq_to_keys[freq + 1].append(key)
    
    def _remove_min_freq_key(self) -> None:
        key = self.freq_to_keys[self.min_freq].pop(0)
        del self.key_to_val[key]
        del self.key_to_freq[key]

public class LFUCache {
    private int capacity;
    private int minFreq;
    private Dictionary<int, int> keyToVal;
    private Dictionary<int, int> keyToFreq;
    private Dictionary<int, LinkedList<int>> freqToKeys;
    private Dictionary<int, LinkedListNode<int>> keyToNode;
    
    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.minFreq = 0;
        this.keyToVal = new Dictionary<int, int>();
        this.keyToFreq = new Dictionary<int, int>();
        this.freqToKeys = new Dictionary<int, LinkedList<int>>();
        this.keyToNode = new Dictionary<int, LinkedListNode<int>>();
    }
    
    public int Get(int key) {
        if (!keyToVal.ContainsKey(key)) {
            return -1;
        }
        IncreaseFreq(key);
        return keyToVal[key];
    }
    
    public void Put(int key, int value) {
        if (capacity <= 0) return;
        
        if (keyToVal.ContainsKey(key)) {
            keyToVal[key] = value;
            IncreaseFreq(key);
            return;
        }
        
        if (keyToVal.Count >= capacity) {
            RemoveMinFreqKey();
        }
        
        keyToVal[key] = value;
        keyToFreq[key] = 1;
        if (!freqToKeys.ContainsKey(1)) {
            freqToKeys[1] = new LinkedList<int>();
        }
        keyToNode[key] = freqToKeys[1].AddLast(key);
        minFreq = 1;
    }
    
    private void IncreaseFreq(int key) {
        int freq = keyToFreq[key];
        freqToKeys[freq].Remove(keyToNode[key]);
        
        if (freqToKeys[freq].Count == 0 && freq == minFreq) {
            minFreq++;
        }
        
        keyToFreq[key] = freq + 1;
        if (!freqToKeys.ContainsKey(freq + 1)) {
            freqToKeys[freq + 1] = new LinkedList<int>();
        }
        keyToNode[key] = freqToKeys[freq + 1].AddLast(key);
    }
    
    private void RemoveMinFreqKey() {
        int key = freqToKeys[minFreq].First.Value;
        freqToKeys[minFreq].RemoveFirst();
        
        keyToVal.Remove(key);
        keyToFreq.Remove(key);
        keyToNode.Remove(key);
    }
}

var LFUCache = function(capacity) {
    this.capacity = capacity;
    this.minFreq = 0;
    this.keyToVal = new Map();
    this.keyToFreq = new Map();
    this.freqToKeys = new Map();
};

LFUCache.prototype.get = function(key) {
    if (!this.keyToVal.has(key)) {
        return -1;
    }
    
    this.increaseFreq(key);
    return this.keyToVal.get(key);
};

LFUCache.prototype.put = function(key, value) {
    if (this.capacity <= 0) return;
    
    if (this.keyToVal.has(key)) {
        this.keyToVal.set(key, value);
        this.increaseFreq(key);
        return;
    }
    
    if (this.keyToVal.size >= this.capacity) {
        this.removeMinFreqKey();
    }
    
    this.keyToVal.set(key, value);
    this.keyToFreq.set(key, 1);
    if (!this.freqToKeys.has(1)) {
        this.freqToKeys.set(1, new Set());
    }
    this.freqToKeys.get(1).add(key);
    this.minFreq = 1;
};

LFUCache.prototype.removeMinFreqKey = function() {
    const keyList = this.freqToKeys.get(this.minFreq);
    const deletedKey = keyList.values().next().value;
    keyList.delete(deletedKey);
    this.keyToVal.delete(deletedKey);
    this.keyToFreq.delete(deletedKey);
};

LFUCache.prototype.increaseFreq = function(key) {
    const freq = this.keyToFreq.get(key);
    this.keyToFreq.set(key, freq + 1);
    
    this.freqToKeys.get(freq).delete(key);
    if (!this.freqToKeys.has(freq + 1)) {
        this.freqToKeys.set(freq + 1, new Set());
    }
    this.freqToKeys.get(freq + 1).add(key);
    
    if (this.freqToKeys.get(freq).size === 0 && freq === this.minFreq) {
        this.minFreq++;
    }
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

操作	时间复杂度	空间复杂度
get	O(1)	-
put	O(1)	-
总空间复杂度	-	O(capacity)

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目