本文共 3681 字，大约阅读时间需要 12 分钟。

1. 题目信息

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作？

示例:LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );cache.put(1, 1);cache.put(2, 2);cache.get(1);       // 返回  1cache.put(3, 3);    // 该操作会使得密钥 2 作废cache.get(2);       // 返回 -1 (未找到)cache.put(4, 4);    // 该操作会使得密钥 1 作废cache.get(1);       // 返回 -1 (未找到)cache.get(3);       // 返回  3cache.get(4);       // 返回  4

来源：力扣（LeetCode）

2. 解题

• 类似题目：

2.1 手动实现list

要 put 和 get 方法的时间复杂度为 O(1)，这个数据结构要：查找快，插入快，删除快，有顺序之分。

• 有顺序之分，区分最近使用的和久未使用的数据
• 容量满了要删除最后一个数据
• 访问时要把数据插入到队头。

哈希表查找快，但数据无顺序

• LRU 缓存算法的核心数据结构就是哈希链表，双向链表和哈希表的组合体。

借一张图表示下哈希链表。

class Node{
   public:    int key, value;    Node *prev, *next;    Node(int k, int v):prev(NULL),next(NULL)    {
           key = k;        value = v;    }};class DoubleList{
       Node *head, *tail;    int len;public:    DoubleList():len(0)    {
           head = new Node(0,0);        tail = new Node(0,0);        head->next = tail;        tail->prev = head;    }    void addAtHead(Node* newnode)    {
           newnode->next = head->next;        newnode->prev = head;        head->next->prev = newnode;        head->next = newnode;        len++;    }    void delNode(Node *del)    {
           del->prev->next = del->next;        del->next->prev = del->prev;        len--;    }    Node* delLast()//删除最后的节点，并返回该节点    {
           if(tail->prev == head)            return NULL;        Node *last = tail->prev;        delNode(last);        return last;    }    int size()    {
           return len;    }};class LRUCache {
       unordered_map
   
     m;    DoubleList cache;    int cap;public:    LRUCache(int capacity) {
           cap = capacity;    }        int get(int key) {
           if(m.find(key) == m.end())            return -1;        int val = m[key]->value;        put(key, val);        return val;    }        void put(int key, int value) {
           Node *newnode = new Node(key,value);        if(m.find(key) != m.end())//找到节点，移至前面        {
               cache.delNode(m[key]);            cache.addAtHead(newnode);            m[key] = newnode;        }        else//没找到key        {
               if(cap == cache.size())            {
                   Node *last = cache.delLast();                m.erase(last->key);            }            cache.addAtHead(newnode);            m[key] = newnode;        }    }};/** * Your LRUCache object will be instantiated and called as such: * LRUCache* obj = new LRUCache(capacity); * int param_1 = obj->get(key); * obj->put(key,value); */
   

2.2 使用内置list

class LRUCache {
       list
   
     cache;    int cap;    unordered_map
    
      kv;    unordered_map
     
      
       ::iterator> kPos;public:    LRUCache(int capacity) {
           cap = capacity;    }        int get(int key) {
           if(!kv.count(key))            return -1;        put(key,kv[key]);        return kv[key];    }        void put(int key, int value) {
           if(kv.count(key))        {
               cache.erase(kPos[key]);            cache.push_front(key);            kPos[key] = cache.begin();            kv[key] = value;        }        else        {
               if(cap == cache.size())            {
                   int lastkey = cache.back();                cache.pop_back();                kv.erase(lastkey);            }            kv[key] = value;            cache.push_front(key);            kPos[key] = cache.begin();        }    }};
      
     
    
   

转载地址：https://michael.blog.csdn.net/article/details/100178189 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！