Why my c++ solution using hash map and list exceeds time limit?


  • 1
    Z
    typedef unordered_map<int, pair<int, list<int>::iterator>> Map;
    class LRUCache{
        int _capacity;
        Map _map;
        list<int> _list;
    public:
        LRUCache(int capacity) : _capacity(capacity) {}
    
        void touch(Map::iterator& it){
            _list.erase(it->second.second);
            _list.push_front(it->first);
            it->second.second = _list.begin();
        }
    
        int get(int key) {
            auto it = _map.find(key);
            if(it!=_map.end()){
                touch(it);
                return it->second.first;
            }
            else{
                return -1;
            }
        }
    
        void set(int key, int value) {
            auto it = _map.find(key);
            if(it!=_map.end()){
                touch(it);
            }
            else{
                _list.push_front(key);
            }
    
            if(_list.size() > _capacity){
                // remove oldest element in q and map
                int tail = _list.back();
                //cout << "**removing key " << tail << endl;
                _map.erase(tail);
                _list.pop_back();
            }
            _map[key] = make_pair(value, _list.begin());
        }
    };

Log in to reply
 

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