k**e
发帖数: 17 | 1 class LRUCache{
public:
int size;
unordered_map M;
list L;
LRUCache(int capacity) {
size = capacity;
}
int get(int key) {
if (M.find(key)==M.end()) return -1;
L.remove(key);
L.push_back(key);
return M[key];
}
void set(int key, int value) {
if (M.find(key)==M.end()) {
if (M.size()
M[key]=value;
L.push_back(key);
}
else {
M.erase(*L.begin());
M[key] = value;
L.pop_front();
L.push_back(key);
}
}
else {
M[key]=value;
L.remove(key);
L.push_back(key);
}
}
}; |
d****n
发帖数: 12461 | 2 map存list里面的iterator
删除用erase，不用find。 |
s**x
发帖数: 7506 | 3 List 要存key , value pair, 或hash table 的相应iteratir plus value pair.
Hash table 的value 应该是相应list 的iterator.
Get 的时候hash table 找到后要通过iterator 去移动在list 中位置。list 删除最后
一个时要通过对应的iteratir 找hash 中的element. |
k**e
发帖数: 17 | 4 感谢回复，但是我还是不理解，为什么map里面要放key和list的iterator?我直接把key
和value存在map里面，然后按访问的次序把keys存一个list,并实时更新，这样有何不
妥？难道这样时间复杂度高吗？请指教，谢谢 |
g****s
发帖数: 340 | 5 对。"L.remove(key)"的complexity是O(n),"iterator erase(const_iterator
position)"的complexity是O(1)。 |
