【每日打卡】[leetcode]460-LFU缓存

马谦马谦马谦
马谦马谦马谦
马谦马谦马谦
614
文章
12
评论
2020年4月5日17:00:11 评论

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/lfu-cache

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

一、题目描述

设计并实现最不经常使用(LFU)缓存的数据结构。它应该支持以下操作:getput

  • get(key) - 如果键存在于缓存中,则获取键的值(总是正数),否则返回 -1。
  • put(key, value) - 如果键不存在,请设置或插入值。当缓存达到其容量时,它应该在插入新项目之前,使最不经常使用的项目无效。在此问题中,当存在平局(即两个或更多个键具有相同使用频率)时,最近最少使用的键将被去除。

进阶:

你是否可以在 O(1) 时间复杂度内执行两项操作?

示例:

二、题目解析

LFU算法是LRU算法的改进版本,LRU算法强调最近最少使用,逐步淘汰掉很久没有使用的缓存。而LFU在LRU的基础上引入了使用频率限制,优先使用频率来淘汰缓存。在频率同等的情况下,再通过LRU淘汰较久没有使用的。

虽然只是增加了一个维度的判断,但是在逻辑和编码上,多出来的麻烦就不止一个档次了。因为题目要求在O(1)的时间复杂度内完成两项操作。对于get操作而言,如果使用哈希表来保存所有的缓存节点,可以在O(1)的时间复杂度完成。但是对于put操作来说,想要把它在O(1)的时间复杂度内插入,就不简单了,必须要有合适的数据结构来支撑才行,因为除了保存频次以外还有记录节点的使用时间。如果像LRU一样使用链表来存,每个缓存节点都要先找到合适的位置才能插入,时间复杂度是O(n)

这里可以采取的方式是使用两个哈希表来保存所有的节点,其中一个以缓存的key值作为哈希表的key,另外一个以缓存出现的频率作为哈希表的key。假设保存所有缓存节点的哈希表为cache,保存频率的哈希表为freq,那么它的操作逻辑为:

【每日打卡】[leetcode]460-LFU缓存

三、代码

马谦马谦马谦
  • 本文由 发表于 2020年4月5日17:00:11
  • 转载请务必保留本文链接:https://www.dyxmq.cn/program/algorithms/leetcode460-lfu-cache.html
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: