来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/lfu-cache
1. 题目
设计并实现最不经常使用(LFU)缓存的数据结构。它应该支持以下操作:get 和 put。
get(key) - 如果键存在于缓存中,则获取键的值(总是正数),否则返回 -1。
put(key, value) - 如果键不存在,请设置或插入值。当缓存达到其容量时,它应该在插入新项目之前,使最不经常使用的项目无效。在此问题中,当存在平局(即两个或更多个键具有相同使用频率)时,最近最少使用的键将被去除。
进阶:
你是否可以在 O(1) 时间复杂度内执行两项操作?
示例:
LFUCache cache = new LFUCache( 2 /* capacity (缓存容量) */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 去除 key 2
cache.get(2); // 返回 -1 (未找到key 2)
cache.get(3); // 返回 3
cache.put(4, 4); // 去除 key 1
cache.get(1); // 返回 -1 (未找到 key 1)
cache.get(3); // 返回 3
cache.get(4); // 返回 4
2.JAVA 代码
创建map保存具体的key、value、和第几层优先级队列,priorityMap保存每一个优先级队列的顺序;时间复杂度O(N),空间复杂度O(N),最难理解的还是在题目意思:
- put方法也会增加该元素的优先级
-
put不存在的元素,一定会剔除一个元素
时间复杂度O(N),空间复杂度O(N)
该代码还能再优化,在map中不止记录优先级队列和值,还得记录优先级队列中的索引,这样就可以避免遍历索引位置的消耗,将时间复杂度提升至O(1)
class LFUCache {
private int maxNum;
private int currentNum;
private Map<Integer,int[]> map;
private Map<Integer,ArrayList<Integer>> priorityMap;
public LFUCache(int capacity) {
maxNum = capacity;
currentNum = 0;
map = new HashMap<>();
priorityMap = new HashMap<>();
}
public int get(int key) {
if(maxNum<=0){
return -1;
}
int[] val = map.get(key);
if(val==null){
return -1;
}
int priority = val[0];
int value = val[1];
map.put(key,new int[]{priority+1,value});
List list = priorityMap.get(priority);
Iterator<Integer> integerIterator = list.iterator();
while(integerIterator.hasNext()){
Integer integer = integerIterator.next();
if(integer == key){
integerIterator.remove();
break;
}
}
list = priorityMap.get(priority+1);
if(list==null){
priorityMap.put(priority+1,new ArrayList<>());
list = priorityMap.get(priority+1);
}
list.add(key);
return value;
}
public void put(int key, int value) {
if(maxNum<=0){
return;
}
// [主程序-遍历]:通过hash查找元素是否存在O(1)
int[] val = map.get(key);
/***
* [主程序-分支]:
* 1.如果不为null,直接对值修改,优先级不变,priority list将元素移动到末尾
* 2.如果为null,得进行判断元素是否满了:
* 2.1 元素满了,需要剔除priority =1得第一个元素,然后追加priority=1得末尾
* 2.2 元素未慢,直接加入,然后追加priority=1的末尾
*/
// 1.如果不为null,直接对值修改,优先级+1
if(val!=null){
int priority = val[0];
map.put(key,new int[]{priority+1,value});
List list = priorityMap.get(priority);
Iterator<Integer> iterator = list.iterator();
while(iterator.hasNext()){
if(iterator.next()==key){
iterator.remove();
break;
}
}
list = priorityMap.get(priority+1);
if(list==null){
priorityMap.put(priority+1,new ArrayList<>());
list = priorityMap.get(priority+1);
}
list.add(key);
return;
}
if(currentNum<maxNum){
currentNum++;
map.put(key,new int[]{1,value});
List<Integer> list = priorityMap.get(1);
if(list==null){
priorityMap.put(1,new ArrayList<>());
list = priorityMap.get(1);
}
list.add(key);
return;
}
int layer = 1;
while(true){
List<Integer> list = priorityMap.get(layer);
if(list.size()==0){
layer++;
continue;
}
Integer keyDel = list.remove(0);
map.put(key,new int[]{1,value});
map.remove(keyDel);
break;
}
List<Integer> list = priorityMap.get(1);
list.add(key);
}
}
/**
* Your LFUCache object will be instantiated and called as such:
* LFUCache obj = new LFUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/
网友评论