LFU缓存

作者: 我知他风雨兼程途径日暮不赏 | 来源:发表于2020-04-05 12:44 被阅读0次

    来源:力扣(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);
     */
    

    相关文章

      网友评论

          本文标题:LFU缓存

          本文链接:https://www.haomeiwen.com/subject/hjhuphtx.html