LeetCode 460 LFU Cache

Tag: 设计数据结构 LeetCode Posted on 2022-02-10 14:45:23 Edited on 2022-02-10 17:45:15 Views: 158

概述

https://leetcode.com/problems/lfu-cache/

注意:

For this problem, when there is a tie (i.e., two or more keys with the same frequency), the least recently used key would be invalidated.

基于优先级队列的失败尝试

第一反应是用最小堆来维护 key 的访问频率。

如果给最小堆加入一个元素,该元素与顶层元素的值相同,其会取代它吗? 不会:

最小堆:每个节点都小于等于它的子节点。

这种情况下顶部元素依然遵循定义,没必要僭越。

时间复杂度 OKay 么?优先级队列的插入和删除元素都是 O(logn),n 为队列中元素个数。 所以应该 Okay。


额,优先级队列没办法访问中间元素啊,我们没办法更新频率。

附上没办法继续写的代码:

class LFUCache {
public:
    int capacity;
    typedef pair<int, int> pi;  // <count, key>
    priority_queue<pi, vector<pi>, greater<pi>> keyQueue;
    unordered_map<int, int> cache;
    LFUCache(int capacity) {
        this->capacity = capacity;
    }
    
    int get(int key) {
        if (cache.count(key) == 0) return -1;
        promote(key);
        return cache[key];        
    }
    
    void put(int key, int value) {
        if (cache.count(key) == 0) {
            if (keyQueue.size() == capacity) {
                evict();
            }
            cache[key] = value;
            keyQueue.emplace({1, key});
        } else {
            cache[key] = value;
            promote(key);
        }
    }
    
    int promote(int key) {
        
    }
    
    int evict() {
        auto key = keyQueue.top().second;
        keyQueue.pop();
        cache[key].erase();
    }
};

基于 Map + 双向链表的实现

https://labuladong.gitee.io/algo/2/20/46/

用到的数据结构:

  1. 一个 map 用来存键与(值,频率)对;
  2. 一个 map 用来存频率与对应的键列表对,注意这里的列表是 LinkedHashSet;

或者:

  1. 一个 map 用来存键与(值,频率)对;
  2. 一个 map 用来存频率与对应的键列表对,注意这里的列表是普通的双向链表;
  3. 一个 map 用来存键与 List 迭代器对(使我们能常数时间内访问链表的任意节点);

下面的实现 Runtime Error 了,因为 LeetCode 用 capacity 为 0 的参数偷袭了我 50 多行的代码。 这样的测试用例好么?这不好,希望 LeetCode 不要再犯这样的小聪明啊。

class LFUCache {
public:
    int capacity;
    int minFreq;
    unordered_map<int, pair<int, int>> cache;  // key -> <value, freq>
    unordered_map<int, list<int>> freq2keyList;  // freq -> [key1, key2, ..., keyn]
    unordered_map<int, list<int>::iterator> pointer;  // key -> iterator
    LFUCache(int capacity) {
        this->capacity = capacity;
    }
    
    int get(int key) {
        if (cache.count(key) == 0) return -1;
        promote(key);
        return cache[key].first;        
    }
    
    void put(int key, int value) {
        if (cache.count(key) != 0) {
            cache[key].first = value;
            promote(key);
            return;
        }
        
        if (cache.size() == capacity) {
            evict();
        }
        
        minFreq = 1;
        cache[key] = {value, minFreq};
        freq2keyList[minFreq].push_front(key);
        pointer[key] = freq2keyList[minFreq].begin();
    }
    
    void promote(int key) {
        int oldFreq = cache[key].second ++ ;
        int newFreq = cache[key].second;
        freq2keyList[oldFreq].erase(pointer[key]);
        if (freq2keyList[oldFreq].empty()) {
            freq2keyList.erase(oldFreq);
            if (minFreq == oldFreq) minFreq = newFreq;
        }
        freq2keyList[newFreq].push_front(key);
        pointer[key] = freq2keyList[newFreq].begin();
    }
    
    void evict() {
        auto key = freq2keyList[minFreq].back();
        freq2keyList[minFreq].pop_back();
        if (freq2keyList[minFreq].empty()) {
            freq2keyList.erase(minFreq);
            // but this time we don't need to care minFreq anymore, cause after evict(), minFreq will be reset to 1
        }
        cache.erase(key);
        pointer.erase(key);
    }
};

在 put() 里加了一行 if (capacity == 0) return; 完事。

未经允许,禁止转载,本文源站链接:https://iamazing.cn/