公众号merlinsea


  • 相关内容导航

LRU最近最少使用算法

奔跑的小梁，公众号：梁霖编程工具库golang实现lru缓存


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

  • 示例
  • 解题思路
    • 参考之前求解LRU的算法思路，改动点是当访问了某个key的时候，这个key需要移动到一个“合适”的位置，这里的合适指的是要按照每个key的访问频次来排序，当频次相同的访问时间越近的key优先级越高。


  • 代码实现



  • 代码优化思路
    • 可以将双向链表做成优先队列，通过优先队列可以保证每次删除的时间复杂度是logn级别，在本次的代码中，在极端的情况下，比如LFU的容量做的无限大的时候，不断进行put操作，会导致move方法的时间复杂度是On


golang版本永久算法题训练营本年最低价～

奔跑的小梁，公众号：梁霖编程工具库