460. LFU Cache (Hard) - TengnanYao/daily_leetcode GitHub Wiki

class LFUCache(object):

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.h = {}
        self.n = capacity
        self.i = 0

    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        if self.h.get(key) == None:
            return -1
        self.h[key][1] += 1
        self.h[key][0] = self.i
        self.i += 1
        return self.h[key][2]

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: None
        """
        if self.n > 0:
            if self.h.get(key) == None:
                if len(self.h) >= self.n:
                    m = min(x[1] for x in self.h.values())
                    k = sorted([a for (a, b) in self.h.items() if b[1] == m], key = lambda x: self.h[x][0])[0]
                    del self.h[k]
            self.h[key] = [self.i, self.h.get(key, [0, 0, 0])[1] + 1, value]
            self.i += 1


# Your LFUCache object will be instantiated and called as such:
# obj = LFUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)