题目：

设计并实现最不经常使用（LFU）缓存的数据结构。它应该支持以下操作：get 和 put。

get(key) - 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。
put(key, value) - 如果键不存在，请设置或插入值。当缓存达到其容量时，它应该在插入新项目之前，使最不经常使用的项目无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，最近最少使用的键将被去除。

进阶：
你是否可以在 O(1) 时间复杂度内执行两项操作？

示例：

LFUCache cache = new LFUCache( 2 /* capacity (缓存容量) */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回 1
cache.put(3, 3);    // 去除 key 2
cache.get(2);       // 返回 -1 (未找到key 2)
cache.get(3);       // 返回 3
cache.put(4, 4);    // 去除 key 1
cache.get(1);       // 返回 -1 (未找到 key 1)
cache.get(3);       // 返回 3
cache.get(4);       // 返回 4

题目的理解：

有效的缓存机制，将不常用的删除：
（1）每次增加，修改或获取，需要将优先级提高1 。
（2）优先级修改后，需要将缓存的顺序也修改。
（3）在新增时，如果缓存已经满了，那么先将优先级最低的删除。

python实现

class LFUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.valueDict = dict()
        self.timesDict = dict()
        self.keysList = list()

    def get(self, key: int) -> int:
        if key not in self.keysList:
            return -1

        value = self.valueDict[key]
        times = self.timesDict[key] + 1
        self.timesDict[key] = times
        self.keysList.remove(key)
        self.move(key, times)

        return value

    def put(self, key: int, value: int) -> None:
        if self.capacity <= 0:
            return

        if key in self.keysList:
            self.valueDict[key] = value

            times = self.timesDict[key] + 1
            self.timesDict[key] = times
            self.keysList.remove(key)
            self.move(key, times)

            return

        if len(self.keysList) >= self.capacity:
            lasttKey = self.keysList.pop()
            self.timesDict.pop(lasttKey)
            self.valueDict.pop(lasttKey)

        self.valueDict[key] = value
        self.timesDict[key] = 1
        self.move(key, 1)

    def move(self, key, times):
        hasInsert = False
        for index, item in enumerate(self.keysList):
            itemTimes = self.timesDict[item]
            if times >= itemTimes:
                hasInsert = True
                self.keysList.insert(index, key)
                break

        if hasInsert is False:
            self.keysList.append(key)

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

想看最优解法移步此处