LeetCode_数据结构设计_困难_460. LFU 缓存

x33g5p2x  于2022-05-11 转载在 其他  
字(3.6k)|赞(0)|评价(0)|浏览(397)

1.题目

请你为最不经常使用(LFU)缓存算法设计并实现数据结构。

实现 LFUCache 类:

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

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

当一个键首次插入到缓存中时,它的使用计数器被设置为 1 (由于 put 操作)。对缓存中的键执行 get 或 put 操作,使用计数器的值将会递增。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例:

  1. 输入:
  2. ["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
  3. [[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
  4. 输出:
  5. [null, null, null, 1, null, -1, 3, null, -1, 3, 4]
  6. 解释:
  7. // cnt(x) = 键 x 的使用计数
  8. // cache=[] 将显示最后一次使用的顺序(最左边的元素是最近的)
  9. LFUCache lfu = new LFUCache(2);
  10. lfu.put(1, 1); // cache=[1,_], cnt(1)=1
  11. lfu.put(2, 2); // cache=[2,1], cnt(2)=1, cnt(1)=1
  12. lfu.get(1); // 返回 1
  13. // cache=[1,2], cnt(2)=1, cnt(1)=2
  14. lfu.put(3, 3); // 去除键 2 ,因为 cnt(2)=1 ,使用计数最小
  15. // cache=[3,1], cnt(3)=1, cnt(1)=2
  16. lfu.get(2); // 返回 -1(未找到)
  17. lfu.get(3); // 返回 3
  18. // cache=[3,1], cnt(3)=2, cnt(1)=2
  19. lfu.put(4, 4); // 去除键 1 ,1 和 3 的 cnt 相同,但 1 最久未使用
  20. // cache=[4,3], cnt(4)=1, cnt(3)=2
  21. lfu.get(1); // 返回 -1(未找到)
  22. lfu.get(3); // 返回 3
  23. // cache=[3,4], cnt(4)=1, cnt(3)=3
  24. lfu.get(4); // 返回 4
  25. // cache=[3,4], cnt(4)=2, cnt(3)=3

提示:
0 <= capacity <= 104
0 <= key <= 105
0 <= value <= 109
最多调用 2 * 105 次 get 和 put 方法

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/lfu-cache

2.思路

(1)数据结构设计
思路参考算法题就像搭乐高:手把手带你拆解 LFU 算法

3.代码实现(Java)

  1. //思路1————数据结构设计
  2. class LFUCache {
  3. //LFU 缓存的最大容量
  4. int capacity;
  5. //LFU 缓存最小的频次
  6. int minFreq;
  7. //key 到 value 的映射
  8. HashMap<Integer, Integer> keyToValue;
  9. //key 到 freq 的映射
  10. HashMap<Integer, Integer> keyToFreq;
  11. //freq 到 key 列表的映射
  12. HashMap<Integer, LinkedHashSet<Integer>> freqToKeys;
  13. public LFUCache(int capacity) {
  14. //初始化
  15. this.capacity = capacity;
  16. this.minFreq = 0;
  17. this.keyToValue = new HashMap<>();
  18. this.keyToFreq = new HashMap<>();
  19. this.freqToKeys = new HashMap<>();
  20. }
  21. public int get(int key) {
  22. if (keyToValue.containsKey(key) == false) {
  23. //未找到该 key
  24. return -1;
  25. } else {
  26. //找到该 key,则其频率加一
  27. increaseFreq(key);
  28. return keyToValue.get(key);
  29. }
  30. }
  31. public void put(int key, int value) {
  32. if (this.capacity <= 0) {
  33. return;
  34. }
  35. if (keyToValue.containsKey(key)) {
  36. /*若 key 已存在,修改其对应的 value 即可*/
  37. keyToValue.put(key, value);
  38. //key 的频率加一
  39. increaseFreq(key);
  40. return;
  41. }
  42. /*若 key 不存在,则需要将其插入*/
  43. if (this.capacity <= keyToValue.size()) {
  44. //LFU 缓存容量已满,则需要淘汰一个 freq 最小的 key
  45. removeMinFreqKey();
  46. }
  47. //将 (key, value) 加入到 keyToValue 中
  48. keyToValue.put(key, value);
  49. //将 (key, 1) 加入到 keyToFreq 中
  50. keyToFreq.put(key, 1);
  51. //更新 freqToKeys
  52. freqToKeys.putIfAbsent(1, new LinkedHashSet<>());
  53. freqToKeys.get(1).add(key);
  54. //插入新 key 后 minFreq 肯定是 1
  55. this.minFreq = 1;
  56. }
  57. //key的频率加一
  58. public void increaseFreq(int key) {
  59. //更新 keyToFreq
  60. int freq = keyToFreq.get(key);
  61. keyToFreq.put(key, freq + 1);
  62. //将 key 从 freq 对应的列表中删除
  63. freqToKeys.get(freq).remove(key);
  64. //将 key 加入 freq + 1 对应的列表中
  65. freqToKeys.putIfAbsent(freq + 1, new LinkedHashSet<>());
  66. freqToKeys.get(freq + 1).add(key);
  67. //如果 freq 对应的列表为空,则移除这个 freq
  68. if (freqToKeys.get(freq).isEmpty()) {
  69. freqToKeys.remove(freq);
  70. //如果这个 freq 恰好是 minFreq,则更新 minFreq
  71. if (freq == this.minFreq) {
  72. this.minFreq++;
  73. }
  74. }
  75. }
  76. //淘汰一个 freq 最小的 key
  77. public void removeMinFreqKey() {
  78. //从 freqToKeys 中找到 freq = minFreq 的列表‘
  79. LinkedHashSet<Integer> keysList = freqToKeys.get(this.minFreq);
  80. //keysList 中最先加入的 key 就是应该被淘汰的 key
  81. int removedKey = keysList.iterator().next();
  82. keysList.remove(removedKey);
  83. if (keysList.isEmpty()) {
  84. //删除 removedKey 后,keysList 为空
  85. freqToKeys.remove(this.minFreq);
  86. /*
  87. 此处不需要更新 minFreq,具体原因如下:
  88. removeMinFreqKey() 在 put() 中插入新 key 时可能会调用,而 put() 的代码中,
  89. 插入新 key 时一定会把 minFreq 更新成 1,所以此处无需更新 minFreq
  90. */
  91. }
  92. //删除 keyToValue 中的 removedKey
  93. keyToValue.remove(removedKey);
  94. //删除 keyToFreq 中的 removedKey
  95. keyToFreq.remove(removedKey);
  96. }
  97. }
  98. /**
  99. * Your LFUCache object will be instantiated and called as such:
  100. * LFUCache obj = new LFUCache(capacity);
  101. * int param_1 = obj.get(key);
  102. * obj.put(key,value);
  103. */

相关文章