Why not using a hash map + linked list?


  • 0
    D

    I red some of the most voted solutions, but I am confused why not just use a hash map to store the key and value pair, use a linked list to track the priority of the keys. my solution exceeds the time limit. anyone could advise why? THANKS!!

    public class LRUCache {
    int cap;
    LinkedList<Integer> cache;
    HashMap<Integer, Integer> map ;
    public LRUCache(int capacity) {
    cache = new LinkedList<Integer>();
    map = new HashMap<Integer, Integer>();
    cap = capacity;
    }

    public int get(int key) {
        int res = -1;
        if (map.containsKey(key)) {
            res = map.get(key);
            cache.remove(Integer.valueOf(key));
            cache.add(key);
        }
        return res;
    }
    
    public void set(int key, int value) {
        if (!map.containsKey(key) ) {
            
            if(map.size() >= cap) {
            int rmkey = cache.poll();
            map.remove(rmkey);
    
             }
            cache.offer(key);
            map.put(key,value);
        }
                else {
            get(key);
            map.put(key,value);
        }
            }
    

    }


  • 0

    Cause the default linkedList is way too slow for the test cases here.

    That's the major reason people choose double linked list, it can be added and deleted all by itself, no other references at all. No loop, so much faster and will help u pass.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.