难度：困难

题目内容：

设计并实现最不经常使用（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

题解：

emmm看着蛮简单的就是有点麻烦
实际上有很多边界条件要考虑。。。
所以对着报错修改了好多好多遍

class LFUCache:

    def __init__(self, capacity: int):
        self.cache = {}        # 每个元素是个长度为2的列表，分别是键值和使用次数
        self.capacity = capacity
        self.keylist = [] #按使用次数顺序排一个key的列表,emmm就倒序吧
    def get(self, key: int) -> int:
        if key in self.cache.keys():
            for i in range(len(self.keylist)):
                if self.keylist[i][0] == key:
                    self.keylist[i][1] += 1
                    if i > 0:
                        if self.keylist[i][1] >= self.keylist [i-1][1]:
                            self.keylist[i],self.keylist[i-1] = self.keylist[i-1],self.keylist[i]
                    break
            return self.cache[key]
        else:
            return -1

    def put(self, key, value):
        if self.capacity == 0:
            return
        if key in self.cache.keys():
            for i in range(len(self.keylist)):
                if self.keylist[i][0] == key:
                    self.keylist.pop(i)
                break
        self.cache[key] = value
        if len(self.cache) > self.capacity  and len(self.keylist)>=1:
            self.cache.pop(self.keylist[-1][0])
            self.keylist.pop()
        self.keylist.append([key,0])
        if len(self.keylist)>1:
            if self.keylist[-2][1] == 0:
                self.keylist[-1],self.keylist[-2] = self.keylist[-2],self.keylist[-1]

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