这是LeetCode上的「.LFU缓存」，难度为「困难」。
Tag:「链表」、「双向链表」、「设计」
请你为「最不经常使用（LFU）」缓存算法设计并实现数据结构。
实现LFUCache类：
LFUCache(intcapacity)-用数据结构的容量capacity初始化对象intget(intkey)-如果键存在于缓存中，则获取键的值，否则返回-1。voidput(intkey,intvalue)-如果键已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量时，则应该在插入新项之前，使最不经常使用的项无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除「最近最久未使用」的键。注意「项的使用次数」就是自插入该项以来对其调用get和put函数的次数之和。使用次数会在对应项被移除后置为0。
为了确定最不常使用的键，可以为缓存中的每个键维护一个使用计数器。使用计数最小的键是最久未使用的键。
当一个键首次插入到缓存中时，它的使用计数器被设置为1(由于put操作)。对缓存中的键执行get或put操作，使用计数器的值将会递增。
示例：
输入：["LFUCache","put","put","get","put","get","get","put","get","get","get"][[2],[1,1],[2,2],[1],[3,3],[2],[3],[4,4],[1],[3],[4]]输出：[null,null,null,1,null,-1,3,null,-1,3,4]解释：//cnt(x)=键x的使用计数//cache=[]将显示最后一次使用的顺序（最左边的元素是最近的）LFUCachelFUCache=newLFUCache(2);lFUCache.put(1,1);//cache=[1,_],cnt(1)=1lFUCache.put(2,2);//cache=[2,1],cnt(2)=1,cnt(1)=1lFUCache.get(1);//返回1//cache=[1,2],cnt(2)=1,cnt(1)=2lFUCache.put(3,3);//去除键2，因为cnt(2)=1，使用计数最小//cache=[3,1],cnt(3)=1,cnt(1)=2lFUCache.get(2);//返回-1（未找到）lFUCache.get(3);//返回3//cache=[3,1],cnt(3)=2,cnt(1)=2lFUCache.put(4,4);//去除键1，1和3的cnt相同，但1最久未使用//cache=[4,3],cnt(4)=1,cnt(3)=2lFUCache.get(1);//返回-1（未找到）lFUCache.get(3);//返回3//cache=[3,4],cnt(4)=1,cnt(3)=3lFUCache.get(4);//返回4//cache=[3,4],cnt(4)=2,cnt(3)=3
提示：
0=capacity,key,value=最多调用
次get和put方法
进阶：你可以为这两种操作设计时间复杂度为
的实现吗？
基本分析前两天我们刚讲过.LRU缓存机制，简单理解LRU就是「移除最久不被使用的元素」。
因此对于LRU我们只需要在使用「哈希表」的同时，维护一个「双向链表」即可：
每次发生get或put的时候就将元素存放双向链表头部当需要移除元素时，则从双向链表尾部开始移除LFU简单理解则是指「移除使用次数最少的元素」，如果存在多个使用次数最小的元素，则移除「最近不被使用的那个」（LRU规则）。同样的get和put都算作一次使用。
因此，我们需要记录下每个元素的使用次数，并且在
的复杂度内「修改某个元素的使用次数」和「找到使用次数最小的元素」。
桶排序+双向链表「我们可以使用「桶排序」的思路，搭配「双向链表」实现
操作。」
「在LFUCache中，我们维护一个由Bucket作为节点的双向链表，每个Bucket都有一个idx编号，代表当前桶存放的是「使用了多少次」的键值对」（idx=1的桶存放使用一次的键值对；idx=2的桶存放的是使用两次的键值对...）。
同时LFUCache持有一个「哈希表」，用来记录哪些key在哪个桶内。
「在Bucket内部则是维护了一条以Item作为节点的双向链表，Item是用作存放真实键值对的。」
同样的，Bucket也持有一个「哈希表」，用来记录key与Item的映射关系。
因此LFUCache其实是一个「链表套链表」的数据结构：
对应到LFUCache的几种操作：
get：先通过LFUCache持有的哈希表进行查找，如果不存在返回，如果存在找到键值对所在的桶cur：调用对应的cur的remove操作，得到键值对对应的item（移除代表当前键值对使用次数加一了，不会在存在于原来的桶中）。将item放到idx为
的桶target中（代表代表当前键值对使用次数加一，应该放到新的目标桶中）。如果目标桶target不存在，则创建；如果原来桶cur移除键值对后为空，则销毁。更新LFUCache中哈希表的信息。put：先通过LFUCache持有的哈希表进行查找：容量达到数量的话需要调用「编号最小的桶」的clear操作，在clear操作内部，会从item双向链表的尾部开始移除元素。完成后再执行插入操作。如果存在：找到键值对所在的桶cur，调用cur的put操作，更新键值对，然后调用LFUCache的get操作实现使用次数加一。如果不存在：先检查容量是否达到数量：插入操作：将键值对添加到
的桶中（代表当前键值对使用次数为
），如果桶不存在则创建。
代码：
classLFUCache{classItem{Iteml,r;intk,v;publicItem(int_k,int_v){k=_k;v=_v;}}classBucket{Bucketl,r;intidx;Itemhead,tail;MapInteger,Itemmap=newHashMap();publicBucket(int_idx){idx=_idx;head=newItem(-1,-1);tail=newItem(-1,-1);head.r=tail;tail.l=head;}voidput(intkey,intvalue){Itemitem=null;if(map.containsKey(key)){item=map.get(key);//更新值item.v=value;//在原来的双向链表位置中移除item.l.r=item.r;item.r.l=item.l;}else{item=newItem(key,value);//添加到哈希表中map.put(key,item);}//增加到双向链表头部item.r=head.r;item.l=head;head.r.l=item;head.r=item;}Itemremove(intkey){if(map.containsKey(key)){Itemitem=map.get(key);//从双向链表中移除item.l.r=item.r;item.r.l=item.l;//从哈希表中移除map.remove(key);returnitem;}returnnull;//never}Itemclear(){//从双向链表尾部找到待删除的节点Itemitem=tail.l;item.l.r=item.r;item.r.l=item.l;//从哈希表中移除map.remove(item.k);returnitem;}booleanisEmpty(){returnmap.size()==0;}}MapInteger,Bucketmap=newHashMap();Buckethead,tail;intn;intcnt;publicLFUCache(intcapacity){n=capacity;cnt=0;head=newBucket(-1);tail=newBucket(-1);head.r=tail;tail.l=head;}publicintget(intkey){if(map.containsKey(key)){Bucketcur=map.get(key);Buckettarget=null;if(cur.r.idx!=cur.idx+1){//目标桶空缺target=newBucket(cur.idx+1);target.r=cur.r;target.l=cur;cur.r.l=target;cur.r=target;}else{target=cur.r;}//将当前键值对从当前桶移除，并加入新的桶Itemremove=cur.remove(key);target.put(remove.k,remove.v);//更新当前键值对所在桶信息map.put(key,target);//如果在移除掉当前键值对后，当前桶为空，则将当前桶删除（确保空间是O(n)的）//也确保调用编号最小的桶的clear方法，能够有效移除掉一个元素deleteIfEmpty(cur);returnremove.v;}return-1;}publicvoidput(intkey,intvalue){if(n==0)return;if(map.containsKey(key)){//元素已存在，修改一下值Bucketcur=map.get(key);cur.put(key,value);//调用一下get实现「使用次数」+1get(key);}else{//容器已满，需要先删除元素if(cnt==n){//从第一个桶（编号最小、使用次数最小）中进行清除Bucketcur=head.r;Itemclear=cur.clear();map.remove(clear.k);cnt--;//如果在移除掉键值对后，当前桶为空，则将当前桶删除（确保空间是O(n)的）//也确保调用编号最小的桶的clear方法，能够有效移除掉一个元素deleteIfEmpty(cur);}//需要将当前键值对增加到1号桶Bucketfirst=null;//如果1号桶不存在则创建if(head.r.idx!=1){first=newBucket(1);first.r=head.r;first.l=head;head.r.l=first;head.r=first;}else{first=head.r;}//将键值对添加到1号桶first.put(key,value);//更新键值对所在桶信息map.put(key,first);//计数器加一cnt++;}}voiddeleteIfEmpty(Bucketcur){if(cur.isEmpty()){cur.l.r=cur.r;cur.r.l=cur.l;cur=null;//helpGC}}}时间复杂度：各操作均为
时间复杂度：
最后
这是我们「刷穿LeetCode」系列文章的第No.篇，系列开始于/01/01，截止于起始日LeetCode上共有道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：