关于力扣 146LRU缓存机制问题
来源：2-1 有趣、简单的算法问题
qq_慕娘3016055
2021-11-24
以下贴上我的代码：
class LRUCache {
int cap;
LinkedList<Integer> list = new LinkedList<>();
HashMap<Integer,Integer> map;
public LRUCache(int capacity) {
this.cap = capacity;
this.map = new HashMap<>(capacity);
}
public int get(int key) {
if (!list.contains(key)) return -1;
list.remove(Integer.valueOf(key));
list.add(key);
return map.get(key);
}
public void put(int key, int value) {
if (list.contains(key)){
list.remove(Integer.valueOf(key));
list.add(key);
map.put(key,value);
}else if (list.size() == cap){
int k = list.removeFirst();
list.add(key);
map.remove(k);
map.put(key,value);
}else {
list.add(key);
map.put(key,value);
}
}
}
我想请问一下，我这个算法超时了，有没有一些优化我这个算法的建议 能够通过
1回答
-
javaman
2021-11-25
同学 您好 List.Remove是线性查找并删除的。
建议把map的value改成list的iterator，这样查找到这个值后，可以直接从list里删除。
122021-11-26
