一个缓存结构需要实现如下功能。 set(key, value)：将记录(key, value)插入该结构 get(key)：返回key对应的value值 但是缓存结构中最多放K条记录，如果新的第K+1条记录要加入，就需要根据策略删掉一条记录，然后才能把新记录加入。这个策略为：在缓存结构的K条记录中，哪一个key从进入缓存结构的时刻开始，被调用set或者get的次数最少，就删掉这个key的记录； 如果调用次数最少的key有多个，上次调用发生最早的key被删除 这就是LFU缓存替换算法。实现这个结构，K作为参数给出 [要求] set和get方法的时间复杂度为O(1)
参数说明：[[1,2,1][1,2,2][2,2][1,2,1]],2 第一个参数是二维数组，数组中第一个元素1表示set 2表示get,第二个参数是key,第三个参数是：val, 第二个参数是缓存的大小：最大存2个内存
import java.util.*; public class LFU{ public Map<Integer,KValue> map = new HashMap<Integer,KValue>(); public int kIndex = 1; public long lastTime = 0; public int[] LFU(int[][] operators, int k){ this.kIndex = k; List<Integer> list = new ArrayList<Integer>(); for(int[] operator : operators){ if(operator[0] == 1){ setValue(operator[1], operator[2]); }else if(operator[0] == 2){ list.add(getValue(operator[1])); } } return list.stream().mapToInt(i -> Integer.valueOf(i)).toArray(); } public void setValue(int key,int val){ //先从map中获取到数据 KValue kv = map.get(key); if(kv == null){ if(map.size() >= kIndex){ //查到map中operatNum最小lastTime最小的数据 KValue[] values = map.values().toArray(new KValue[0]); int minKey = values[0].key; long minLastTime = values[0].lastTime; int minOptNum = values[0].operatNum; int len = values.length; for(int i=1;i<len;i++){ KValue kval = values[i]; int k = kval.key; if((kval.operatNum < minOptNum) || (kval.operatNum == minOptNum && kval.lastTime < minLastTime)){ minKey = k; minOptNum = kval.operatNum; minLastTime = kval.lastTime; } } map.remove(minKey); } kv = new KValue(); kv.key = key; kv.val = val; kv.operatNum = kv.operatNum + 1; kv.lastTime = lastTime++; map.put(key, kv); }else{ kv.key = key; kv.val = val; kv.operatNum = kv.operatNum + 1; kv.lastTime = lastTime++; } } //获取值 public int getValue(int key){ KValue kv = map.get(key); if(kv == null){ return -1; } kv.lastTime = lastTime++; kv.operatNum = kv.operatNum + 1; return kv.val; } } class KValue{ public int key; public int val; public int operatNum; public long lastTime; }