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

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

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