Simple python solution using ordereddict with O(1) operations


  • 0
    Y
    class LFUCache(object):
    
        def __init__(self, capacity):
            self.d = collections.defaultdict(int)
            self.num = collections.defaultdict(collections.OrderedDict)
            self.cap = capacity
            self.min = 1
            
    
        def get(self, key):
            if key not in self.d:
                return -1
            value = self.num[self.d[key]][key]
            self.update(key, value)
            return value
    
    
        def put(self, key, value):
            self.update(key, value)
            
            
        def update(self, key, value):
            count = self.d[key]
            self.d[key] = count + 1
            if count: self.num[count].pop(key)
            self.num[count + 1][key] = value
            if len(self.d) > self.cap:
                first, _ = self.num[self.min].popitem(last=False)
                self.d.pop(first)
            if count == self.min and not self.num[count]:
                self.min = count + 1
            else:
                self.min = min(self.min, count + 1)
    

Log in to reply
 

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