【数据结构】460. LFU 缓存

460. LFU 缓存

解题思路

• get操作 返回key对应的val 然后增加对应的freq
• 插入操作 如果key已经存在 直接进行更新 如果不存在 但是容器已经满了 直接进行删除freq最小的Key 之后进行插入

class LFUCache {// key到  val的映射   KVHashMap<Integer,Integer> keyToVal;// 从key到freq的映射  KFHashMap<Integer,Integer> keyToFreq;// 一个频率对应多个 key  舍弃最久未使用的  FKHashMap<Integer,LinkedHashSet<Integer>> freqToKeys;// 记录最小的频率int minFreq;// 记录LFU 缓存的最大容量int cap;public LFUCache(int capacity) {keyToVal = new HashMap<>();keyToFreq = new HashMap<>();freqToKeys = new HashMap<>();this.cap = capacity;this.minFreq = 0;}// 返回对应key的val  然后增加对应的freqpublic int get(int key) {if(!keyToVal.containsKey(key)){return -1;// 返回-1  说明没找到}// 增加key对应的freq + 1  因为查找操作一次increaseFreq(key);return keyToVal.get(key);// 找到val}public void put(int key, int value) {// 如果key 已经存在直接更新if(this.cap <= 0){return;}if(keyToFreq.containsKey(key)){// 修改val即可keyToVal.put(key,value);// 对应的freq加一increaseFreq(key);return;}// key 不存在  需要插入 如果容量没有满 直接插入  如果已满 直接删除 freq最小的keyif(this.cap <= keyToVal.size()){removeMinFreqKey();// 删除freq最小的key}keyToVal.put(key,value);keyToFreq.put(key,1);// 插入KF 表  一种freq对应多种keyfreqToKeys.putIfAbsent(1,new LinkedHashSet<>());freqToKeys.get(1).add(key);// 获取频率  添加一种key// 插入新的key之后最小的freq肯定是1this.minFreq = 1;}private void removeMinFreqKey(){// freq最小的key列表  通过 FKLinkedHashSet<Integer> keyList = freqToKeys.get(this.minFreq);// 获取所有的key// 最先被插入的key就是该被淘汰的keyint deleteKey = keyList.iterator().next();// 更新FK keyList.remove(deleteKey);if(keyList.isEmpty()){// 如果key列表是空的  说明都没有了直接删除freqfreqToKeys.remove(this.minFreq);}// 更新KVkeyToVal.remove(deleteKey);// 更新KFkeyToFreq.remove(deleteKey);}private void increaseFreq(int key){int freq = keyToFreq.get(key);// 更新 KFkeyToFreq.put(key,freq + 1);// 更新FK// 将key 从freq对应的列表中删除freqToKeys.get(freq).remove(key);// 将key加入freq + 1 对应的列表freqToKeys.putIfAbsent(freq + 1,new LinkedHashSet<>());// 创建新的freqToKeys.get(freq + 1).add(key);// 如果对应的列表空if(freqToKeys.get(freq).isEmpty()){freqToKeys.remove(freq);if(freq == this.minFreq){this.minFreq++;}}}
}/*** Your LFUCache object will be instantiated and called as such:* LFUCache obj = new LFUCache(capacity);* int param_1 = obj.get(key);* obj.put(key,value);*/