【数据结构】460. LFU 缓存

460. LFU 缓存

解题思路

• get操作 返回key对应的val 然后增加对应的freq
• 插入操作 如果key已经存在 直接进行更新 如果不存在 但是容器已经满了 直接进行删除freq最小的Key 之后进行插入

class LFUCache {
           // key到  val的映射   KV
        HashMap<Integer,Integer> keyToVal;

        // 从key到freq的映射  KF
        HashMap<Integer,Integer> keyToFreq;

        // 一个频率对应多个 key  舍弃最久未使用的  FK
        HashMap<Integer,LinkedHashSet<Integer>> freqToKeys;
        // 记录最小的频率
        int minFreq;

        // 记录LFU 缓存的最大容量
        int cap;

    public LFUCache(int capacity) {
        keyToVal = new HashMap<>();
        keyToFreq = new HashMap<>();
        freqToKeys = new HashMap<>();
        this.cap = capacity;
        this.minFreq = 0;
    }
    // 返回对应key的val  然后增加对应的freq
    public int get(int key) {

        if(!keyToVal.containsKey(key)){
            return -1;// 返回-1  说明没找到
        }

        // 增加key对应的freq + 1  因为查找操作一次
        increaseFreq(key);
        return keyToVal.get(key);// 找到val

    }

    public void put(int key, int value) {
        // 如果key 已经存在直接更新

        if(this.cap <= 0){
            return;
        }

        if(keyToFreq.containsKey(key)){
            // 修改val即可
            keyToVal.put(key,value);
            // 对应的freq加一
            increaseFreq(key);

            return;
        }


        // key 不存在  需要插入 如果容量没有满 直接插入  如果已满 直接删除 freq最小的key


        if(this.cap <= keyToVal.size()){
            removeMinFreqKey();// 删除freq最小的key
        }


        keyToVal.put(key,value);

        keyToFreq.put(key,1);

        // 插入KF 表  一种freq对应多种key
        freqToKeys.putIfAbsent(1,new LinkedHashSet<>());


        freqToKeys.get(1).add(key);// 获取频率  添加一种key

        // 插入新的key之后最小的freq肯定是1

        this.minFreq = 1;


    }


    private void removeMinFreqKey(){
        // freq最小的key列表  通过 FK
        LinkedHashSet<Integer> keyList = freqToKeys.get(this.minFreq);// 获取所有的key

        // 最先被插入的key就是该被淘汰的key
        int deleteKey = keyList.iterator().next();

        // 更新FK 
        keyList.remove(deleteKey);

        if(keyList.isEmpty()){
            // 如果key列表是空的  说明都没有了直接删除freq
            freqToKeys.remove(this.minFreq);
        }

        // 更新KV
        keyToVal.remove(deleteKey);

        // 更新KF
        keyToFreq.remove(deleteKey);

    }

    private void increaseFreq(int key){
        int freq = keyToFreq.get(key);

        // 更新 KF
        keyToFreq.put(key,freq + 1);

        // 更新FK

        // 将key 从freq对应的列表中删除
        freqToKeys.get(freq).remove(key);

        // 将key加入freq + 1 对应的列表
        freqToKeys.putIfAbsent(freq + 1,new LinkedHashSet<>());// 创建新的
        freqToKeys.get(freq + 1).add(key);

        // 如果对应的列表空
        if(freqToKeys.get(freq).isEmpty()){
            freqToKeys.remove(freq);
            if(freq == this.minFreq){
                this.minFreq++;
            }
        }
    }
}

/**
 * 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);
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133