NC94：设计LFU缓存结构

LFU算法：least frequently used，最近最不经常使用算法；

如果一个数据在最近一段时间很少被访问到，那么可以认为在将来它被访问的可能性也很小。因此，当空间满时，最小频率访问的数据最先被淘汰。

• set(key,value)：将记录(key,value)插入该结构。当缓存满时，将访问频率最低的数据置换掉。
• get(key)：返回key对应的value值。

一般会维护两个数据结构：

• 哈希：用来提供对外部的访问，查询效率更高；
• 双向链表或队列：维护了对元素访问次数的排序

缓存操作导致的链表变化：

1. 添加新元素：新元素访问次数为1，放到队尾；
2. 缓存淘汰：从队尾开始淘汰，因为队尾元素的访问次数最少；
3. 访问缓存：访问缓存会增加元素的访问次数，所以元素在队列或双向链表中的位置会重新排序
   

解法1：双哈希表

import java.util.*;
import java.util.Map.Entry;

public class Solution {
    /**
     * lfu design
     * @param operators int整型二维数组 ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public int[] LFU (int[][] operators, int k) {
        // write code here
        if(operators==null) 
            return new int[] {-1};
        LinkedHashMap<Integer, Integer> map = new LinkedHashMap<Integer, Integer>();
        LinkedHashMap<Integer, Integer> count = new LinkedHashMap<Integer, Integer>();
        ArrayList<Integer> list  = new ArrayList<Integer>();
        for(int i=0;i<operators.length;i++) {
            int op = operators[i][0];
            int key = operators[i][1];
            if(op==1) {
                if(map.containsKey(key)) {
                    map.put(key, operators[i][2]);
                    count.put(key, count.get(key)+1);
                }else {
                    if(map.size()==k) {
                        int removekey = GetMinKey(count);
                        map.remove(removekey);
                        count.remove(removekey);
                    }
                    map.put(key, operators[i][2]);
                    if(count.containsKey(key)) 
                        count.put(key, count.get(key)+1);
                    else 
                        count.put(key, 1);    
                }
            }
            else if(op==2) {
                if(map.containsKey(key)) {
                    int val = map.get(key);
                    count.put(key, count.get(key)+1);
                    list.add(val);
                }else {
                    list.add(-1);
                }
            }
        }
        int []A = new int [list.size()];
        for(int i=0;i<list.size();i++) {
            A[i] = list.get(i);
        }
        return A;
    }

    public int GetMinKey(LinkedHashMap<Integer, Integer> count) {
        int minCount = Integer.MAX_VALUE;
        int key = 0;
        for(Entry<Integer, Integer> entry : count.entrySet()) {
            if(entry.getValue()<minCount) {
                minCount = entry.getValue();
                key = entry.getKey();
            }
        }
        return key;
    }
}