Python efficient solution using queue + hash


  • 0
    C

    The basic idea is to make a queue as "history log", which stores all events sequentially (i.e. ordered by time). And we just need to keep popping out the keys till we find one that doesn't have any duplicate in the queue, meaning it's "older" than any other keys and it wasn't visited for the rest of the time, i.e. the LRU one.

    And to keep track of their duplicates, a separate hash is used.

    class LRUCache(object):
        def __init__(self, capacity):
            """
            :type capacity: int
            """
            from collections import deque
            self.queue = deque()
            self.cap = capacity
            self.cache = {}
            self.cnt = {}
    
        def get(self, key):
            """
            :type key: int
            :rtype: int
            """
            if key in self.cache:
                self.queue.append(key)
                self.cnt[key] += 1
                return self.cache[key]
            else:
                return -1
    
        def put(self, key, value):
            """
            :type key: int
            :type value: int
            :rtype: void
            """
            self.cache[key] = value
            self.queue.append(key)
    
            if key in self.cache:
                self.cnt[key] += 1
            else:
                self.cnt[key] = 1
    
                while len(self.cache) > self.cap:
                    k = self.queue.popleft()
                    self.cnt[k] -= 1
                    if self.cnt[k] == 0:
                        del self.cnt[k]
                        del self.cache[k]
    

Log in to reply
 

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