My 273 ms Python Solution


  • 0
    M

    Using list and dict to reduce the complexity to O(log). Just not to 'pop' old ones.

    class LRUCache:
    
        # @param capacity, an integer
        def __init__(self, capacity):
            self.capacity = capacity
            self.pos = self.cnt = 0
            self.record = {}
            self.queue = []
    
        def _update(self):
            while self.cnt > self.capacity:
                key = self.queue[self.pos]
                if self.record[key][0] > 1:
                    self.record[key][0] -= 1
                else:
                    del self.record[key]
                    self.cnt -= 1
                self.pos += 1
    
        # @return an integer
        def get(self, key):
            if key in self.record:
                self.queue.append(key)
                self.record[key][0] += 1
                return self.record[key][1]
            return -1
    
        # @param key, an integer
        # @param value, an integer
        # @return nothing
        def set(self, key, value):
            if key in self.record:
                self.queue.append(key)
                self.record[key][0] += 1
                self.record[key][1] = value
            else:
                self.queue.append(key)
                self.record[key] = [1, value]
                self.cnt += 1
            self._update()

Log in to reply
 

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