LFU Cache
原题链接LFU Cache
实现LFU置换算法，置换规则是当容量满时换出使用频率最少的那个，不考虑一定时间内的频率的情况下，可以采用每个页使用的次数作为判断依据，相当于从创建之初到现在的使用频率
类似的置换算法为了在效率上有一定的保障，通常都是空间换时间，本题也明确规定的时间复杂度是O(1)，而O(1)多数情况下都是类似map的存储结构，当然，C++中map和set是采用红黑树实现的，效率是O(lgN)，而另一个采用hashtable实现的unordered_map和unordered_set则是O(1)的效率
接下来考虑采用map保存的数据
首先为了根据键key找到值value和它的使用频率freq，可以考虑保存一个类似unordered_map<int, std::pair<int, int>>的结构代表键到\<值，频率>的映射。称为keyToVF
接下来考虑当容量满时进行置换的情况，为了让效率进一步提升，可以借鉴类似操作系统内核处理不同状态进程控制块时的策略，即每种状态的进程控制块维护一个链表，这里就只需为每个频率维护一个链表，再存储在map中，即unordered_map<int, list<int>>结构代表频率freq到保存键的链表的映射。称为fToList
但是这样仍然不够，没有办法确定某一时刻最小的频率是多少，所以还需要使用一个变量记录当前最小使用频率minF，当置换时，直接从fToList[minF]中移除一个页，这里可以事先规定，新加入的都添加到链表尾部，移除则移除头部
当调用get函数时需要对键key的频率进行增加，从keyToVF中可以找到key对应的值和频率，从fToList中可以找到频率对应的链表，需要做的事情是从这个链表中删除key，然后添加到fToList[freq+1]这个链表中。由于链表删除与key相等的节点时需要遍历链表，而删除指定迭代器处的节点时只需要改变几个指针，所以为了更进一步提高速度，再次使用一个map保存键key到key在链表中迭代器的映射即unordered_map<int, list<int>::iterator>。称为keyToIt
至此三个map都已经构造完成，get和put的工作只是在线性时间操作不同的map而已
代码如下
class LFUCache {public:LFUCache(int capacity) {capacity_ = capacity;size_ = 0;minF_ = 1;}int get(int key) {/* 不存在key */if(keyToVF_.find(key) == keyToVF_.end()) return -1;/* 将key从key的频率map中删除，然后加到freq+1的链表中 */fToList_[keyToVF_[key].second].erase(keyToIt_[key]);fToList_[++keyToVF_[key].second].push_back(key);keyToIt_[key] = --fToList_[keyToVF_[key].second].end();/* 更新最小频率 */if(fToList_[minF_].empty())++minF_;return keyToVF_[key].first;}void put(int key, int value) {if(capacity_ == 0) return;/* 将频率加一，返回非-1表示存在key，重新设置value即可 */if(get(key) != -1){keyToVF_[key].first = value;return;}if(size_ == capacity_){/* 删除频率最小的链表头 */keyToVF_.erase(fToList_[minF_].front());keyToIt_.erase(fToList_[minF_].front());fToList_[minF_].pop_front();--size_;}/* 添加数据到频率为1的链表中 */keyToVF_[key] = std::make_pair(value, 1);fToList_[1].push_back(key);keyToIt_[key] = --fToList_[1].end();minF_ = 1;++size_;}private:unordered_map<int, std::pair<int, int>> keyToVF_;unordered_map<int, list<int>::iterator> keyToIt_;unordered_map<int, list<int>> fToList_;int capacity_;int size_;int minF_;};/*** 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);*/
今天才发现csdn的markdown的<>是敏感字符….
如果觉得《每天一道LeetCode-----实现LFU置换算法》对你有帮助，请点赞、收藏，并留下你的观点哦！
