I think the average is O(1), but why it's so slow? Any suggestion?


  • 0
    Y

    I use a dict to store the value with a priority like this:

    {key:[priority, value]}

    When the cache is not full, increase the max priority and set the priority of the unit to the max priority, it's O(1) in a dict. When the cache is full, it needs to find the key with the min priority, then delete it, it's O(n).

    class LRUCache:
    
    # @param capacity, an integer
    def __init__(self, capacity):
        self.maxPriority=1
        self.cache={}
        self.capacity=capacity
    
    # @return an integer
    def get(self, key):
        if key in self.cache:
            self.cache[key][0]=self.maxPriority+1
            self.maxPriority+=1
            return self.cache[key][1]
        return -1
    
    # @param key, an integer
    # @param value, an integer
    # @return nothing
    def set(self, key, value):
        if key not in self.cache:
            if self.capacity>0:
                self.capacity-=1
            else:
                oldkey=min(self.cache,key=lambda k:self.cache[k][0])
                del self.cache[oldkey]
        self.cache[key]=[self.maxPriority+1,value]
        self.maxPriority+=1

Log in to reply
 

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