汇芳书院

专注计算机视觉、机器学习、分布式计算等领域, 兼聊投资、写作、生活

0%

460. LFU 缓存

发表于 更新于 分类于 Valine：
本文字数： 4.9k 阅读时长 ≈ 4 分钟

请你为 最不经常使用（LFU）缓存算法设计并实现数据结构。

实现 LFUCache 类：

LFUCache(int capacity) - 用数据结构的容量 capacity 初始化对象 int get(int key) - 如果键 key 存在于缓存中，则获取键的值，否则返回 -1 。 void put(int key,
int value) - 如果键 key 已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量 capacity
时，则应该在插入新项之前，移除最不经常使用的项。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最近最久未使用 的键。 为了确定最不常使用的键，可以为缓存中的每个键维护一个 使用计数器
。使用计数最小的键是最久未使用的键。

当一个键首次插入到缓存中时，它的使用计数器被设置为 1 (由于 put 操作)。对缓存中的键执行 get 或 put 操作，使用计数器的值将会递增。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

 

示例：

输入：
[“LFUCache”, “put”, “put”, “get”, “put”, “get”, “get”, “put”, “get”, “get”, “get”]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
输出：
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]

解释：
// cnt(x) = 键 x 的使用计数

// cache=[] 将显示最后一次使用的顺序（最左边的元素是最近的） LFUCache lfu = new LFUCache(2); lfu.put(1, 1); //
cache=[1,_], cnt(1)=1 lfu.put(2, 2);

// cache=[2,1], cnt(2)=1, cnt(1)=1 lfu.get(1);

// 返回 1

// cache=[1,2], cnt(2)=1, cnt(1)=2 lfu.put(3, 3);

// 去除键 2 ，因为 cnt(2)=1 ，使用计数最小

// cache=[3,1], cnt(3)=1, cnt(1)=2 lfu.get(2);

// 返回 -1（未找到）
lfu.get(3);

// 返回 3

// cache=[3,1], cnt(3)=2, cnt(1)=2 lfu.put(4, 4);

// 去除键 1 ，1 和 3 的 cnt 相同，但 1 最久未使用

// cache=[4,3],
cnt(4)=1, cnt(3)=2 lfu.get(1);

// 返回 -1（未找到） lfu.get(3);

// 返回 3

// cache=[3,4], cnt(4)=1, cnt(3)=3 lfu.get(4);

// 返回 4

// cache=[3,4], cnt(4)=2, cnt(3)=3

提示：

0 <= capacity <= 104 0 <= key <= 105 0 <= value <= 109 最多调用 2 * 105 次 get 和 put 方法

使用哈希表+平衡二叉树

最好使用堆，但是堆支持动态更新非头节点，使用平衡二叉树替代

时间复杂度O(logn)
空间复杂度O(capacity)

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
struct Node{
    int key, value, time, cnt;
    Node(int _key, int _value, int _time, int _cnt):key(_key),value(_value),time(_time),cnt(_cnt){}
    bool operator< (const Node& node) const{
        return cnt == node.cnt ? time < node.time : cnt < node.cnt; 
    }
};

class LFUCache {
    // cache容量和时间戳
    int capacity, timestamp;
    // 平衡二叉查找树，红黑树
    set<Node> S;
    // 无序map
    unordered_map<int, Node> hash_table;
public:
    LFUCache(int _capacity) {
        capacity = _capacity;
        S.clear();
        hash_table.clear();
        // 当前时间戳初始化为0
        timestamp = 0;
    }
    
    int get(int key) {
        if (capacity == 0) return -1;
        auto it = hash_table.find(key);
        if (it == hash_table.end()) return -1;
        Node cache = it->second;
        S.erase(cache);
        cache.time = ++timestamp;
        cache.cnt += 1;
        S.insert(cache);
        it->second = cache;
        return cache.value;
    }
    
    void put(int key, int value) {
        if (capacity == 0) return ;
        auto it = hash_table.find(key);
        // 未找到相同元素，新增
        if (it == hash_table.end()){
            // 存储已满，需要剔除频次最小，时间最久的一个元素
            if (hash_table.size() == capacity){
                hash_table.erase(S.begin()->key);
                S.erase(S.begin());
            }
            Node cache = Node(key, value, ++timestamp, 1);
            S.insert(cache);
            hash_table.insert(make_pair(key, cache));
        }else{ //更新
            Node cache = it->second;
            S.erase(cache);
            cache.time = ++timestamp;
            cache.cnt += 1;
            cache.value = value;
            S.insert(cache);
            it->second = cache;
        }


    }
};

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

两个哈希表

一个哈希表frequency_table存储频率和对应频率下的节点，使用双向链表解决冲突，
队头的节点是最近的节点，队尾的节点是较久的节点。
每个节点存储，key，value，freq

一个哈希表key_table存储key和对应缓存在双向链表中的地址。

时间复杂度变为O(1)

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
struct Node{
    int key, value, freq;
    Node(int _key, int _value, int _freq):key(_key),value(_value),freq(_freq){}
};

class LFUCache {
    int minfreq, capacity;
    unordered_map<int, list<Node>> freq_table;
    unordered_map<int, list<Node>::iterator> key_table;
public:
    LFUCache(int _capacity) {
        capacity = _capacity;
        minfreq = 0;
        freq_table.clear();
        key_table.clear();
    }
    
    int get(int key) {
        if (capacity == 0) return -1;
        auto it = key_table.find(key);
        if (it == key_table.end()) return -1;
        list<Node>::iterator node = it->second;
        int freq = node->freq;
        int value = node->value;
        //需要更新频率
        freq_table[freq].erase(node);
        if (freq_table[freq].size() == 0){
            freq_table.erase(freq);
            if (freq == minfreq) minfreq += 1;
        }
        freq_table[freq+1].push_front(Node(key, value, freq+1));
        key_table[key] = freq_table[freq+1].begin();
        return value;
    }
    
    void put(int key, int value) {
        if (capacity == 0) return ;
        auto it = key_table.find(key);
        // 未找到相同元素，新增
        if (it == key_table.end()){
            // 存储已满，需要剔除频次最小，时间最久的一个元素
            if (key_table.size() == capacity){
                // back返回的是最后一个元素的引用
                auto it2 = freq_table[minfreq].back();
                key_table.erase(it2.key);
                freq_table[minfreq].pop_back();
                if (freq_table[minfreq].size() == 0){
                    freq_table.erase(minfreq);
                }
            }
            freq_table[1].push_front(Node(key, value, 1));
            key_table[key] = freq_table[1].begin();
            minfreq = 1;
        }else{ //更新
            // iterator相当于指针，也表示内存地址，*node则为一个Node对象。访问对象成员变量用, 指针访问变量用->
            list<Node>::iterator node = it->second;
            int freq = node->freq;
            freq_table[freq].erase(node);
            if (freq_table[freq].size() == 0){
                freq_table.erase(freq);
                if (freq == minfreq) minfreq+=1;
            }
            freq_table[freq+1].push_front(Node(key, value, freq+1));
            key_table[key] = freq_table[freq+1].begin();
        }


    }
};

/**
 * 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);
 */
坚持原创分享，您的支持将鼓励我继续创作

欢迎关注我的其它发布渠道

------------- 本文结束,感谢阅读 如有问题可留言交流 -------------