My 273 ms Python Solution

• 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()``````

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