描述

题目描述

一个缓存结构需要实现如下功能。

set(key, value)：将记录(key, value)插入该结构
get(key)：返回key对应的value值

示例

输入：
[[1,1,1],[1,2,2],[1,3,2],[1,2,4],[1,3,5],[2,2],[1,4,4],[2,1]],3
返回值：[4,-1]
说明：
在执行"1 4 4"后，"1 1 1"被删除。因此第二次询问的答案为-1

知识点：模拟、数据结构、LRU、哈希

难度：⭐⭐⭐

题解

图解：

方法一：双哈希

解题思路：

维护两个LinkedHashMap，一个保存元素，一个保存key对应的使用频次

算法流程：

维护两个LinkedHashMap，一个保存元素，一个保存key对应的使用频次
put过程
- 已经使用过该key，map替换value值并增加使用频次
- 第一次使用到这个key，需要判断map容量，容量不足，需要淘汰key
- 容量足，直接put即可
get过程, 从map获取val时，要增加该key的使用频次

Java 版本代码如下：

import java.util.*;


public class Solution {
    public int[] LFU(int[][] operators, int k) {
        // 保存元素
        LinkedHashMap<Integer, Integer> map = new LinkedHashMap<Integer, Integer>();
        // 保存key对应的使用频次
        LinkedHashMap<Integer, Integer> keyToFreq = new LinkedHashMap<Integer, Integer>();
        // 收集结果
        ArrayList<Integer> list = new ArrayList<>();

        for (int i = 0; i < operators.length; i++) {
            int operator = operators[i][0];
            int key = operators[i][1];
            // put过程
            if (operator == 1) {
                // 已经使用过该key，map替换
                if (map.containsKey(key)) {
                    map.put(key, operators[i][2]);
                    keyToFreq.put(key, keyToFreq.get(key) + 1);
                } else {
                    // 第一次使用到这个key，需要判断map容量
                    // 容量不足，需要淘汰key
                    if (map.size() == k) {
                        // 根据使用频次获取最少频次的元素
                        int removekey = GetMinKey(keyToFreq);
                        // 两个map都要删除该key
                        map.remove(removekey);
                        keyToFreq.remove(removekey);
                    }
                    // 容量足，直接put即可
                    map.put(key, operators[i][2]);
                    keyToFreq.put(key, keyToFreq.getOrDefault(key, 0) + 1);
                }
            } else if (operator == 2) {
                // get过程, 从map获取val时，要增加该key的使用频次
                if (map.containsKey(key)) {
                    int val = map.get(key);
                    keyToFreq.put(key, keyToFreq.get(key) + 1);
                    list.add(val);
                } else {
                    list.add(-1);
                }
            }
        }
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }

    public int GetMinKey(LinkedHashMap<Integer, Integer> keyToFreq) {
        int minCount = Integer.MAX_VALUE;
        int key = 0;
        // 遍历每个key，找出使用频次最少的key
        for (Map.Entry<Integer, Integer> entry : keyToFreq.entrySet()) {
            if (entry.getValue() < minCount) {
                minCount = entry.getValue();
                key = entry.getKey();
            }
        }
        return key;
    }

}

复杂度分析：

时间复杂度 $O (1)$ ：put和get时间负责度都是常量

空间复杂度 $O (N)$ ：需要用到map和List，N为元素长度

方法二：模拟

Java 版本代码如下：

import java.util.*;


public class Solution {
    /**
     * lfu design
     * @param operators int整型二维数组 ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    class node{
        // 存放使用频次，key，value
        int freq;
        int key;
        int val;
        public node(){}
        public node(int key, int val, int freq){
            this.freq=freq;
            this.key=key;
            this.val=val;
        }
    }
    int minFreq = 1;
    int size = 0;
    Map<Integer, node>map=new HashMap<>();
    Map<Integer, LinkedList<node>>freqMap=new HashMap<>();

    // 更新node的使用频次，同时根据使用频次freq更新node在链表中的位置
    public void update(node n){
        LinkedList<node>list=freqMap.get(n.freq);
        list.remove(n);
        if(list.isEmpty() && minFreq==n.freq) {
            minFreq++;
        }
        n.freq++;
        if(!freqMap.containsKey(n.freq)) {
            freqMap.put(n.freq, new LinkedList<>());
        }
        LinkedList<node>tmp=freqMap.get(n.freq);
        tmp.addLast(n);
    }
    public int get(int key){
        if(!map.containsKey(key))return -1;
//        从map获取val时，要增加该key的使用频次
        node tmp=map.get(key);
        update(tmp);
        return tmp.val;
    }

    // put过程
    public void put(int key, int val, int k){
        // 已经使用过该key，map替换value值并增加使用频次
        if(map.containsKey(key)){
            node tmp=map.get(key);
            tmp.val=val;
            update(tmp);
            map.put(key, tmp);
            return;
        }

        LinkedList<node>list=freqMap.get(minFreq);
        // 第一次使用到这个key，需要判断map容量，容量不足，需要淘汰key
        if(size==k){
            node tmp=list.removeFirst();
            map.remove(tmp.key);
        }else {
            size++;
        }
        node no=new node(key, val, 1);
        map.put(key, no);
        if(!freqMap.containsKey(1)){
            freqMap.put(1, new LinkedList<node>());
        }
        freqMap.get(1).addLast(no);
        minFreq=1;
    }
    public int[] LFU (int[][] operators, int k) {
        ArrayList<Integer> res = new ArrayList<>();
        for (int i = 0; i < operators.length; i++){
            if (operators[i][0] == 1){
                put(operators[i][1], operators[i][2], k);
            }else{
                res.add(get(operators[i][1]));
            }
        }
        int[] ans = new int[res.size()];
        for (int i = 0; i < ans.length; i++){
            ans[i] = res.get(i);
        }
        return ans;
    }
}

复杂度分析：

时间复杂度 $O (1)$ ：get和put都没有用到循环遍历等操作

空间复杂度 $O (N)$ ：使用了两个Map，N为元素数量

题解 | #LFU缓存结构设计#

描述

题解

方法一：双哈希

方法二：模拟