来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lfu-cache

1. 题目

设计并实现最不经常使用（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);       // 返回 1
cache.put(3, 3);    // 去除 key 2
cache.get(2);       // 返回 -1 (未找到key 2)
cache.get(3);       // 返回 3
cache.put(4, 4);    // 去除 key 1
cache.get(1);       // 返回 -1 (未找到 key 1)
cache.get(3);       // 返回 3
cache.get(4);       // 返回 4

2.JAVA 代码

创建map保存具体的key、value、和第几层优先级队列，priorityMap保存每一个优先级队列的顺序；时间复杂度O(N)，空间复杂度O(N)，最难理解的还是在题目意思:

• put方法也会增加该元素的优先级

• put不存在的元素，一定会剔除一个元素

  
  时间复杂度O(N)，空间复杂度O(N)

该代码还能再优化，在map中不止记录优先级队列和值，还得记录优先级队列中的索引，这样就可以避免遍历索引位置的消耗，将时间复杂度提升至O(1)

class LFUCache {
   private int maxNum;
    private int currentNum;
    private Map<Integer,int[]> map;
    private Map<Integer,ArrayList<Integer>> priorityMap;
    public LFUCache(int capacity) {
        maxNum = capacity;
        currentNum = 0;
        map = new HashMap<>();
        priorityMap = new HashMap<>();
    }

    public int get(int key) {
        if(maxNum<=0){
            return -1;
        }
        int[] val = map.get(key);
        if(val==null){
            return -1;
        }
        int priority = val[0];
        int value = val[1];
        map.put(key,new int[]{priority+1,value});
        List list = priorityMap.get(priority);
        Iterator<Integer> integerIterator = list.iterator();
        while(integerIterator.hasNext()){
            Integer integer = integerIterator.next();
            if(integer == key){
                integerIterator.remove();
                break;
            }
        }
        list = priorityMap.get(priority+1);
        if(list==null){
            priorityMap.put(priority+1,new ArrayList<>());
            list = priorityMap.get(priority+1);
        }
        list.add(key);
        return value;
    }

    public void put(int key, int value) {
        if(maxNum<=0){
            return;
        }
        // [主程序-遍历]：通过hash查找元素是否存在O(1)
        int[] val = map.get(key);
        /***
         *  [主程序-分支]：
         *      1.如果不为null,直接对值修改，优先级不变，priority list将元素移动到末尾
         *      2.如果为null,得进行判断元素是否满了：
         *          2.1 元素满了，需要剔除priority =1得第一个元素，然后追加priority=1得末尾
         *          2.2 元素未慢，直接加入，然后追加priority=1的末尾
         */
        //  1.如果不为null,直接对值修改，优先级+1
        if(val!=null){
            int priority = val[0];
            map.put(key,new int[]{priority+1,value});
            List list = priorityMap.get(priority);
            Iterator<Integer> iterator = list.iterator();
            while(iterator.hasNext()){
                if(iterator.next()==key){
                    iterator.remove();
                    break;
                }
            }
            list = priorityMap.get(priority+1);
            if(list==null){
                priorityMap.put(priority+1,new ArrayList<>());
                list = priorityMap.get(priority+1);
            }
            list.add(key);
            return;
        }

        if(currentNum<maxNum){
            currentNum++;
            map.put(key,new int[]{1,value});
            List<Integer> list = priorityMap.get(1);
            if(list==null){
                priorityMap.put(1,new ArrayList<>());
                list = priorityMap.get(1);
            }
            list.add(key);
            return;
        }
        int layer = 1;
        while(true){
            List<Integer> list = priorityMap.get(layer);
            if(list.size()==0){
                layer++;
                continue;
            }
            Integer keyDel = list.remove(0);
            map.put(key,new int[]{1,value});
            map.remove(keyDel);
            break;
        }
        List<Integer> list = priorityMap.get(1);
        list.add(key);

    }
}

/**
 * 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);
 */