题意整理
设计LRU（最近最少使用）缓存结构，结构有两个功能：get和set，且大小固定为K，set操作超出长度K时删除最少使用的内容，get或set操作的内容立马刷新为最常使用，要求set和get操作的时间复杂度为。
思路
要求get和set操作都为复杂度：
- get操作为
，首先想到的是字典，即哈希表，哈希表能够在
- set操作为
下面实现了两种方法，分别使用自己实现的双向链表和STL中实现的list与哈希表一起实现LRU缓存结构。自己实现的双向链表没有实现的set和get功能，受限于需要查找元素，复杂度在
。
方法一 自己实现双向链表与哈希表进行组合
自己实现了一个双向链表类，data域存键值对的key值，set或get操作时，都用双向链表维护key值的优先级，被get的key从原处挪到链表头部，set时直接插入到头部，如果长度超过K值则删除尾部元素。另外用一个哈希表进行键值对的保存。
示例
输入：[[1,1,1],[1,2,2],[1,3,2],[2,1],[1,4,4],[2,2]],3
代码
class BiDirectionLinkList {
private:
struct node {//双向链表结点
node* pre;
node* next;
int key;
node() : key(-1), pre(NULL), next(NULL) {};
};
node* head;
node* tail;
int length;
public:
BiDirectionLinkList() {//构造函数
head = new node;//头结点
tail = new node;//尾节点
head->next = tail;
tail->pre = head;
length = 0;
}
void insert(int k) {//插入新元素，头插法
node* temp = new node;
temp->key = k;
temp->pre = head;
temp->next = head->next;
head->next->pre = temp;
head->next = temp;
length++;
}
int remove() {//删除链表最后一个元素,并返回该值
node* temp = tail->pre;
temp->pre->next = tail;
tail->pre = temp->pre;
int k = temp->key;
length--;
delete temp;
return k;
}
void update(int k) {//访问元素后将该元素位置更新到头结点后面
//找到k所在结点p
node* p = head->next;
while (p->key != k) {
p = p->next;
}
//将p结点从原处删除
node* q = p->pre;
p->next->pre = q;
q->next = p->next;
//将p结点插入头结点
p->pre = head;
p->next = head->next;
head->next->pre = p;
head->next = p;
}
void travel() {
node* p = head->next;
while (p != tail)
cout << p->key << " ";
}
int size() {
return length;
}
};
class Solution {
public:
/**
* lru design
* @param operators int整型vector<vector<>> the ops
* @param k int整型 the k
* @return int整型vector
*/
BiDirectionLinkList linkList; //双向链表
map<int, int > hashMap; //哈希表,存储键值对
void set(int key, int value, int k) {
if (hashMap.count(key)) {//插入的key已经存在，更新key的位置及对应的value
linkList.update(key);
hashMap[key] = value;
}
else {//数据不在map中，插入数据
if (linkList.size() == k) {//如果linkList长度已满k,删除最后一个元素
int temp = linkList.remove();
hashMap.erase(temp);
}
linkList.insert(key);
hashMap[key] = value;
}
}
int get(int key) {
if (hashMap.count(key)) {//如果存在key，取值，更新缓存
linkList.update(key);
return hashMap[key];
}
else
return -1;
}
vector<int> LRU(vector<vector<int> >& operators, int k) {
// write code here
vector<int> res; //存储结果
int n = operators.size();
for (int i = 0; i < n; i++) {
vector<int> temp = operators[i];
if (temp.size() == 2)//get 操作
res.push_back(get(operators[i][1]));
else// set操作
set(operators[i][1], operators[i][2], k);
}
return res;
}
};复杂度分析
时间复杂度：,由于自己的实现的双链表，在对元素位置进行更新时，需要遍历链表以寻找被更新的元素，查找的复杂度为
,因此set最坏的情况下复杂度为
,get也为
,总的复杂度为
。
空间复杂度：,双链表和哈希表消耗空间都为
。
方法二 使用STL的list和哈希进行组合
STL的list也是双链表，能够进行快速插入与删除，但利用其迭代器的功能，在链表中存储键值对，在哈希中直接存储键值对在链表中的位置，这样在get时可以直接获得键值对在链表中的位置，进而取值，并直接更替元素的位置，set时同理。
代码
class Solution {
public:
/**
* lru design
* @param operators int整型vector<vector<>> the ops
* @param k int整型 the k
* @return int整型vector
*/
list<pair<int, int>> linkList; //双向链表
map<int, list<pair<int, int>>::iterator> hashMap; //哈希表,存储键值对
void set(int key, int value, int k) {
if (hashMap.count(key)) {//插入的key已经存在，更新key的位置及对应的value
linkList.erase(hashMap[key]);
linkList.push_front({key,value});
hashMap[key] = linkList.begin();
}
else {//数据不在map中，插入数据
if (linkList.size() == k) {//如果linkList长度已满k,删除最后一个元素
auto temp = linkList.back();
linkList.pop_back();
hashMap.erase(temp.first);
}
linkList.push_front({key, value});
hashMap[key] = linkList.begin();
}
}
int get(int key) {
if (hashMap.count(key)) {//如果存在key，取值，更新缓存
auto temp = hashMap[key];
linkList.erase(hashMap[key]);
linkList.push_front({key,temp->second});
hashMap[key] = linkList.begin();
return temp->second;
}
else
return -1;
}
vector<int> LRU(vector<vector<int> >& operators, int k) {
// write code here
vector<int> res; //存储结果
int n = operators.size();
for (int i = 0; i < n; i++) {
vector<int> temp = operators[i];
if (temp.size() == 2)//get 操作
res.push_back(get(operators[i][1]));
else// set操作
set(operators[i][1], operators[i][2], k);
}
return res;
}
};复杂度分析
时间复杂度：获得答案的复杂度为,由于不需要进行查找，set和get操作复杂度都为
。
空间复杂度：,list和哈希表消耗空间都为
。
京公网安备 11010502036488号