My O(1) solution


  • 0
    H

    The cache itself is just a normal map as most people will imagine. Use a list of the key to implement LRU. when a key is accessed, move the key to the end of the list. when the cache is full, remove the key at the front of list. These are all O(1) operations for linked list. Also use an addtional map for locating the position of a key in the list in O(1).

    class LRUCache{
    public:
        LRUCache(int capacity) {
            this->capacity = capacity;
        }
        
        int get(int key) {
            if(mp.count(key)>0)
            {
                moveToEnd(key);
                return mp[key];
            }
            return -1;
        }
        
        void set(int key, int value) {
            if(mp.count(key)>0)
            {    
                mp[key]=value;
                moveToEnd(key);
            }
            else if(mp.size()<capacity)
            {
                mp[key]=value;
                l.push_back(key);
                pos[key]=getLast(l);
            }
            else
            {
                mp.erase(l.front());
                l.pop_front();
                mp[key]=value;
                l.push_back(key);
                pos[key]=getLast(l);
            }
    
        }
        void moveToEnd(int key)
        {
            l.erase(pos[key]);
            l.push_back(key);
            list<int>::iterator i= l.end();
            i--;
            pos[key]=i;
        }
        list<int>::iterator getLast(list<int> &l)
        {
            auto it = l.end();
            it--;
            return it;
        }
    private:
        map<int,int> mp;
        map<int,list<int>::iterator> pos;
        list<int> l;
        int capacity;
    };

  • 0
    R

    Hi,
    I tested your code and it passed OJ. But I have a question:

    when you move a key to the end of the list, you update the position for that key. But since you change the position for the new visited key, all keys after that new key are shifted by 1 in the list, shouldn't you update the positions for all keys after the new visited key in the list?


  • 0
    H

    No shift happens, it's linked list.


  • 0
    R

    Thanks! I didn't know that.


  • 2
    K

    Your solution is not O(1), actually it is logarithmic in size of map. Because count function and operator '[ ]' have time complexity of O(log (size of map)).


  • 0
    H

    your are right because i uses map, how about changing to unordered_map?


  • 0
    K

    Yes, using unordered_map will make it O(1),


  • 0
    V

    changing to unordered_map will increase the complexity to O(n). Best you can get is O(logn).


  • 5
    D

    As map in STL is implimented by red-black tree, so it's O(logN)


  • 0
    B

    Why? Unordered_map is O(1) indeed


  • 0
    V

    Finding a key in unordered_map takes O(n) because elements are not stored in sorted order.


  • 0
    R

    no, unordered_map is implemented by hashtable, so It's O(1) indeed.


  • 0
    T

    l.erase(pos[key]);
    This line is O(n)


  • 0
    H

    it's O(1), STL list is double linked list, you just need to modify the "next" field of the prior node.


  • 0
    T

    Ahh so in STL list you can pass in a node to remove. In Java i dont think i am able to do that if i use LinkedList<T>. Have to write my own version to achieve this.


  • 0
    E

    @ vishwas.neo: You're completely wrong. I suggest you read the book The C++ Standard Library, A tutorial and reference. "All standardized unordered container classes are implemented as hash tables, which nonetheless still have a variety of implementation options. " "Assuming that the hashing strategy is well chosen and
    well implemented, you can guarantee amortized constant time for insertions, deletions, and element search "


  • 0
    E

    The question says that "Set or insert the value if the key is not already present". Doesn't it imply that you should not insert or set if the key is already present?


  • 0
    V

    @eaglesky1990: I am not completely wrong dude. In worst case its linear in size of map. But when we are considering millions of operations, than on average its constant. And that is called amortized analysis. Don't just copy paste it. Try to have a better understanding.


  • 1

    I like the way you handled the list, O(1) time :D.
    But, yes as others said, stl::map is O(lg n). So your solution is not O(1); but you can tell, if there was a const time map, then this algo would have worked in const time.


Log in to reply
 

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