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置换算法》对你有帮助,请点赞、收藏,并留下你的观点哦!