OJ says limited time exceed!!!


  • 0
    K

    What's wrong with my idea? The OJ says limited time exceed!!!
    I don't know which part of my answer is slow

    class LRUCache{
    public:
        int size;
        unordered_map<int,int> visited;
        list<int> least_used; //front is the most recently used, end is the least recently used.
        LRUCache(int capacity) {
            size = capacity;
        }
        
    int get(int key) {
        int ret = -1;
        if(visited.find(key) != visited.end()){
            ret = visited[key];
            least_used.remove(key);
            least_used.push_front(key);
        }
        return ret;
    }
    
    void set(int key, int value) {
        if(visited.find(key) != visited.end()){
            least_used.remove(key);
            least_used.push_front(key);
        }else{
            if(least_used.size() < size){
                least_used.push_front(key);
                visited[key] = value;
            }else{
                int remove_key = least_used.back();
                visited.erase(remove_key);
                least_used.pop_back();
                least_used.push_front(key);
                visited[key] = value;
            }
        }
    }
    

    };


  • 0
    Y

    I met the exact same problem, guess pop_back and push_front cost a lot of time in list.


  • 0
    K

    I don't think so, Because popback cost O(n) for linkedlist, and pushfront cost O(1) for linked list, what do you think?


  • 0
    V

    No, pop_back and push_front are constant-time operations. See the "complexity" section at http://www.cplusplus.com/reference/list/list/pop_back/


Log in to reply
 

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