设计/map-困难-leetcode. LRU缓存机制

不知道LRU的同学可以看看操作系统关于页面置换规则的部分或直接百度百科。这里我就不搬砖了。

这道题要实现的话，我认为难度其实算中等。主要难度在于如何实现O(1)时间复杂度。由于存在key->value，因此我们必定需要一个map和一个list，map存储key对应的指针（或指向列表中迭代器），list存储实际的（key，value）单元。可能有同学有疑问，map为什么不直接存value，list为什么存了value还要存key。实际上，如果只是单纯的put和get操作，我们使用一个map存储key->value即可,但是由于我们需要实现LRU的机制。因此，必须有一个list，list中元素的位置表示元素的优先级，每个元素被访问时，我们就将该元素提至list首部，当存储空间满时，list尾部的元素必然要删除，同时map中的位置也要删除，因此，list必然要有元素在map中对应的位置key。同时，每次get之后，都要删除list中元素的位置，同时重新在list首部插入该元素，为了便于查找元素在list中的位置。因此，map中不直接存储value，而是存储list中国年对应元素为first的迭代器。

需要注意的是，C++中，map的查找时间复杂度不是常数，是对数函数，因为其底层实现是红黑树。hash_map和unordered_map才是常数复杂度，但是内存利用率不高，因为底层有很多桶（详情自行百度hash map算法），数据少的时候都是闲置的。在微软的文档中，hash_map不推荐使用，用unordered_map替代（不知道为什么，但是用起来感觉是一样的，接口都没变）。

还有一点也是要注意的，C++中list::size()是O(n)的复杂度计算list长度，效率太低，建议直接自己定义变量存储listsize，并实时更新

最后上代码

class LRUCache {
private:
    int cache_capacity = 0;
    int used = 0;
    list<pair<int, int>> cache;  // 第一个是元素在map中的key 第二个是value
    unordered_map<int, list<pair<int, int>>::iterator> key_cache_map;      // 映射key与元素在list中的位置
public:
    LRUCache() {
        cache_capacity = 0;
    }

    LRUCache(int capacity) {
        cache_capacity = capacity;
    }
    
    int get(int key) {
        auto result = key_cache_map.find(key);
        if (key_cache_map.end() == result) {
            return -1;
        }

        // 每次get将元素重新提至list首部的过程
        // 可以视作将元素删除后再次执行put的过程
        put(key, key_cache_map[key]->second);

        return key_cache_map[key]->second;
    }

    void put(int key, int value) {
        auto find = key_cache_map.find(key);
        if (find != key_cache_map.end()) {
            // 如果key已存在则移除元素
            cache.erase(find->second);
            key_cache_map.erase(find);
            used--;
        } else if (cache_capacity <= used) {
            cout << "full rm " << cache.back().first << endl;
            // 空间已满 移除末尾元素
            key_cache_map.erase(cache.back().first);
            cache.pop_back();
            used--;
        }

        // 插入元素至list头部并更新map
        pair<int, int> p = make_pair(key, value);
        cache.push_front(p);
        key_cache_map[key] = cache.begin();
        used++;
    }
};

提交结果如下
设计/map-困难-leetcode. LRU缓存机制

用stl的LinkedHashMap也能很容易实现不过那样难度就更低了，我就不搬砖了，有兴趣的可以百度~

设计/map-困难-leetcode. LRU缓存机制

相关推荐