0460. LFU Cache =============== 题目信息 -------- :题号: 0460 :难度: Hard :主题: 缓存设计、访问频率、最久未使用、固定容量 :原题: `LeetCode 0460 `_ :重点: ``get`` 和更新已有键都会增加频率、满容量时先淘汰最低频率、频率并列时淘汰最久未使用、操作平均 ``O(1)`` 题目重述 -------- 实现固定容量的 ``LFUCache``。``get(key)``:键存在时返回其值并把使用频率增加 1;键不存在时返回 ``-1``。``put(key, value)``:若键已存在,更新其值并把频率增加 1;若键不存在,则插入频率为 1 的新键。 插入新键前若缓存已满,先删除使用频率最低的键;若有多个键频率相同,则删除其中最久未使用的键。一次成功的 ``get`` 或对已有键的 ``put`` 都算一次使用,会更新并列淘汰所依据的新近程度。 ``capacity`` 位于 ``[0, 10^4]``;键位于 ``[0, 10^5]``,值位于 ``[0, 10^9]``,总调用次数不超过 ``2 * 10^5``。容量为 0 时任何 ``put`` 都不能保存数据。``get`` 和 ``put`` 都要求平均 ``O(1)`` 时间。 自建示例 -------- 频率较低的键先被淘汰: .. code-block:: text 初始:capacity = 2 调用:put(1,10), put(2,20), get(1), put(3,30), get(2), get(3) 查询输出:10、-1、30 解释:get(1) 后键 1 的频率为 2,键 2 的频率仍为 1;插入键 3 时淘汰键 2。 容量为零: .. code-block:: text 初始:capacity = 0 调用:put(5,50), get(5) 查询输出:-1 解释:零容量缓存不能保存任何键值对。 频率桶内用访问顺序解决并列 -------------------------- 用一个按频率编号的双向链表集合保存键:同一频率的键位于同一个桶内,链表头是最近使用,尾部是最久未使用。哈希表把每个键映射到其值、频率和链表迭代器,因此可以在 ``O(1)`` 时间从旧桶删除并放入频率加一的新桶。 额外维护 ``minFrequency``。新键总是进入频率 1 的桶;淘汰时直接取最低频率桶的尾节点。若某频率桶被移空且它正是最低频率,就把最低频率提升到下一桶。 C++ 实现 -------- .. code-block:: cpp class LFUCache { struct Entry { int value; int frequency; std::list::iterator position; }; int capacity; int minFrequency = 0; std::unordered_map entries; std::unordered_map> buckets; void touch(int key) { Entry& entry = entries[key]; int oldFrequency = entry.frequency; auto bucketIt = buckets.find(oldFrequency); bucketIt->second.erase(entry.position); if (bucketIt->second.empty()) { buckets.erase(bucketIt); if (minFrequency == oldFrequency) ++minFrequency; } ++entry.frequency; buckets[entry.frequency].push_front(key); entry.position = buckets[entry.frequency].begin(); } public: LFUCache(int capacity) : capacity(capacity) {} int get(int key) { auto it = entries.find(key); if (it == entries.end()) return -1; touch(key); return entries[key].value; } void put(int key, int value) { if (capacity == 0) return; auto it = entries.find(key); if (it != entries.end()) { it->second.value = value; touch(key); return; } if (entries.size() == static_cast(capacity)) { auto& leastUsed = buckets[minFrequency]; int victim = leastUsed.back(); leastUsed.pop_back(); if (leastUsed.empty()) buckets.erase(minFrequency); entries.erase(victim); } buckets[1].push_front(key); entries[key] = {value, 1, buckets[1].begin()}; minFrequency = 1; } }; 代码分析 -------- 频率哈希表定位桶,链表迭代器定位桶内节点,二者合起来使访问、升频和淘汰都不需要遍历。链表头插保证同频时最新访问在前,尾删正好淘汰最久未使用者;每个操作的平均时间复杂度为 ``O(1)``,空间复杂度为 ``O(capacity)``。