460. LFU Cache O(1)算法 C++

2019-11-10 19:32:38

字体：大中小

来源：转载

供稿：网友

LeetCode 460.LFU Cache的解法，算法时间复杂度为O(1).实际在Leetcode平台跑所耗时间为126ms，基本上超越96%吧主要使用了双重链表和hash表的数据结构来实现，hash用于快速查找，双重链表用于替换策略和存储。#include <list>#include <unordered_map>struct Node{ int key; int value; std::list<struct FreqList>::iterator parent;};struct FreqList{ std::list<struct Node> FList; int Freq;};class LFUCache{public: LFUCache(int capacity); ~LFUCache(); void put(int key, int value); int get(int key);PRivate: std::list<struct FreqList> CacheList; std::unordered_map<int,std::list<struct Node>::iterator > hash_map; int capacity; int size;};using namespace std;LFUCache::LFUCache(int capacity):capacity(capacity),size(0){ struct FreqList flst; flst.Freq = 1; CacheList.push_front(flst);}LFUCache::~LFUCache(){}void LFUCache::put(int key, int value){ if(capacity <= 0) return; unordered_map<int, list<struct Node>::iterator>::iterator got; list<struct FreqList>::reverse_iterator clst_rit; list<struct FreqList>::iterator clst_it; list<struct Node>::iterator nd_it; struct Node nd; nd.key = key; nd.value = value; //在cache存在记录，先插入，后删除，最后更新hash_table got = hash_map.find(key); if (got != hash_map.end()) { //比较大小，看是重新建立一个还是使用上一个FreqList int current_freq, pre_freq; nd_it = hash_map[key]; clst_it = nd_it->parent; current_freq = clst_it->Freq; list<struct FreqList>::iterator current_clst_it; current_clst_it = clst_it; if (clst_it != CacheList.begin()) { --clst_it; } pre_freq = clst_it->Freq; //删除记录 current_clst_it->FList.erase(nd_it); if (pre_freq == current_freq + 1)//前一个刚好是后一个+1的关系，直接插入到前一个的头部即可 { nd.parent = clst_it; clst_it->FList.push_front(nd); } else //否则需要在当前的CacheList节点前重新建立一个FreqList节点 { struct FreqList flst_nd; flst_nd.Freq = current_freq + 1; clst_it = CacheList.insert(current_clst_it,flst_nd); nd.parent = clst_it; clst_it->FList.push_front(nd); } //若为空则删除CacheList的节点 if (current_clst_it->FList.size() == 0) { CacheList.erase(current_clst_it); } //更新hash表 hash_map[key] = clst_it->FList.begin(); } //在Cache中不存在记录，且Cache未满,直接插入即可 else if (size < capacity) { clst_rit = CacheList.rbegin(); //假如最后一个Freq不是1，则创建一个 if (clst_rit->Freq != 1) { struct FreqList flst_tmp; flst_tmp.Freq = 1; CacheList.push_back(flst_tmp); clst_rit = CacheList.rbegin(); } nd.parent = CacheList.end(); nd.parent--; clst_rit->FList.push_front(nd); //更新hash_table hash_map[key] = clst_rit->FList.begin(); size++; } else//Cache中不存在，且Cache已满，寻找合适位置替换即可 { //根据hash记录需要删除的条目 list<struct FreqList>::reverse_iterator flst_last_rit; list<struct Node>::reverse_iterator nd_last_rit; flst_last_rit = CacheList.rbegin(); nd_last_rit = flst_last_rit->FList.rbegin(); int delete_key = nd_last_rit->key; //添加，删除,同步hash表 //1.添加 clst_rit = CacheList.rbegin(); //假如最后一个Freq不是1，则创建一个 if (clst_rit->Freq != 1) { struct FreqList flst_tmp; flst_tmp.Freq = 1; CacheList.push_back(flst_tmp); clst_rit = CacheList.rbegin(); } nd.parent = CacheList.end(); nd.parent--; clst_rit->FList.push_front(nd); //2.删除 list<struct FreqList>::iterator parent; list<struct Node>::iterator nd_delete_it; nd_delete_it = hash_map[delete_key]; parent = nd_delete_it->parent; parent->FList.erase(nd_delete_it); hash_map.erase(delete_key); //FreqList大小为0，删除该节点 if (parent->FList.size() == 0) { CacheList.erase(parent); } //3.同步hash表 hash_map[key] = clst_rit->FList.begin(); }}int LFUCache::get(int key){ if(capacity <= 0) return -1; struct Node nd; int ret = -1; unordered_map<int, list<struct Node>::iterator>::iterator got; list<struct Node>::iterator nd_it; list<struct FreqList>::iterator clst_it; got = hash_map.find(key); if (got != hash_map.end()) { nd_it = hash_map[key]; ret = nd_it->value; clst_it = nd_it->parent; nd.key = key; nd.value = nd_it->value; //修改使用频率，修改，删除，同步 //比较大小，看是重新建立一个还是使用上一个FreqList int current_freq, pre_freq; current_freq = clst_it->Freq; list<struct FreqList>::iterator current_clst_it; current_clst_it = clst_it; if (clst_it != CacheList.begin()) { --clst_it; } pre_freq = clst_it->Freq; //删除记录 current_clst_it->FList.erase(nd_it); if (pre_freq == current_freq + 1)//前一个刚好是后一个+1的关系，直接插入到前一个的头部即可 { nd.parent = clst_it; clst_it->FList.push_front(nd); } else //否则需要在当前的CacheList节点前重新建立一个FreqList节点 { struct FreqList flst_nd; flst_nd.Freq = current_freq + 1; clst_it = CacheList.insert(current_clst_it, flst_nd); nd.parent = clst_it; clst_it->FList.push_front(nd); } if (current_clst_it->FList.size() == 0) { CacheList.erase(current_clst_it); } hash_map[key] = clst_it->FList.begin(); } return ret;}

上一篇：C++拾趣——类构造函数的隐式转换

下一篇：c++