设计并实现最不经常使用（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); // 返回 1cache.put(3, 3); // 去除 key 2cache.get(2); // 返回 -1 (未找到key 2)cache.get(3); // 返回 3cache.put(4, 4); // 去除 key 1cache.get(1); // 返回 -1 (未找到 key 1)cache.get(3); // 返回 3cache.get(4); // 返回 4
思路：这道题可以参考上一篇LRU：
LFU多了一个频率值的计算，只有当频率值相同的时候，才按照LRU那种方式进行排列，即最近最不经常使用的淘汰。
借鉴一种思想，因为时间复杂度是O(1)，所以不能用循环遍历，方法就是采用3个HashMap和1个LinkedHashSet。
第一个hashMap存储put进去的key和value，第二个HashMap存储每个key的频率值，第三个hashMap存储每个频率的相应的key的值的集合。LinkedHashSet存储key的集合，这里用HashSet是因为其是由HashMap底层实现的，可以O(1)时间复杂度查找元素，而且linked是有序的，同一频率值越往后越最近访问。
直接上代码：
import java.util.HashMap;import java.util.LinkedHashSet;class LFUCache { public int capacity;//容量大小 public HashMap map = new HashMap<>();//存储put进去的key和value public HashMap frequent = new HashMap<>();//存储每个key的频率值 //存储每个频率的相应的key的值的集合，这里用HashSet是因为其是由HashMap底层实现的，可以O(1)时间复杂度查找元素 //而且linked是有序的，同一频率值越往后越最近访问 public HashMap > list = new HashMap<>(); int min = -1;//标记当前频率中的最小值 public LFUCache(int capacity) { this.capacity = capacity; } public int get(int key) { if(!map.containsKey(key)){ return -1; }else{ int value = map.get(key);//获取元素的value值 int count = frequent.get(key); frequent.put(key, count + 1); list.get(count).remove(key);//先移除当前key //更改min的值 if(count == min && list.get(count).size() == 0) min++; LinkedHashSet set = list.containsKey(count + 1) ? list.get(count + 1) : new LinkedHashSet (); set.add(key); list.put(count + 1, set); return value; } } public void put(int key, int value) { if(capacity <= 0){ return; } //这一块跟get的逻辑一样 if(map.containsKey(key)){ map.put(key, value); int count = frequent.get(key); frequent.put(key, count + 1); list.get(count).remove(key);//先移除当前key //更改min的值 if (count == min && list.get(count).size() == 0) min++; LinkedHashSet set = list.containsKey(count + 1) ? list.get(count + 1) : new LinkedHashSet (); set.add(key); list.put(count + 1, set); }else{ if(map.size() >= capacity){ Integer removeKey = list.get(min).iterator().next(); list.get(min).remove(removeKey); map.remove(removeKey); frequent.remove(removeKey); } map.put(key, value); frequent.put(key, 1); LinkedHashSet set = list.containsKey(1) ? list.get(1) : new LinkedHashSet (); set.add(key); list.put(1, set); min = 1; } } public static void main(String[] args) { LFUCache lfuCache = new LFUCache(2); lfuCache.put(2, 1); lfuCache.put(3, 2); System.out.println(lfuCache.get(3)); System.out.println(lfuCache.get(2)); lfuCache.put(4, 3); System.out.println(lfuCache.get(2)); System.out.println(lfuCache.get(3)); System.out.println(lfuCache.get(4)); }}
原题链接：