关于力扣 146LRU缓存机制问题

Question

以下贴上我的代码：

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);

        }

    }

}

我想请问一下，我这个算法超时了，有没有一些优化我这个算法的建议 能够通过

Answer 1

javaman 2021-11-25 11:41:21

同学 您好 List.Remove是线性查找并删除的。

建议把map的value改成list的iterator，这样查找到这个值后，可以直接从list里删除。

• 提问者 qq_慕娘3016055 #1

  不太懂老师的意思，请问可以有一句示例代码吗

• javaman 回复 提问者 qq_慕娘3016055 #2

  您好。我的意思是list.Remove效率非常低，每次需要线性查找。这个在get和put中一共出现了3次。
  
  比较简单的方法是把HashMap换成LinkedListMap，因为LinkedListMap可以保证迭代顺序。然后get和put从map中查找后，如果能找到，都需要把原始的key/value从map中删掉，再插入。而且LinkedListMap仍然可以使用RemoveFirst之类的方法，时间复杂度是常数的。
  
  替换为LinkedListMap后，就不需要单独的list了。
  
  
  之前给的想法是把HashMap<Integer, Integer>换成HashMap<Integer, ListIterator<Integer>> 这样会比较麻烦，要同时维护list和map，并且可能需要不断调用listIterator(int index)来获得这个迭代器，复杂度也不低。