题目

解答

这道题目的关键点在于：O(1)时间复杂度内完成查找的操作，虽然使用hash_map的话肯定可以实现O(1)时间复杂度的查询，但是如果只使用hash_map的话，我们这里就难以实现删除元素了。所以这里的想法是：

应该使用链表的结构（list）来存储每一对（key，value），然后用hash_map来记录key对应的（key，value）在list中的迭代器，那么在put操作删除“已经在capacity中但是又被put进来的”元素、删除最近最少使用元素这两种元素的时候，时间复杂度也还是O(1)，而在get操作的查找也显然是O(1)时间复杂度的。

代码如下：

class LRUCache {
private:
    int cap;
    int count;
    unordered_map< int, list< pair<int, int> >::iterator > m;
    list< pair<int ,int> > queue;
public:
    LRUCache(int capacity) {
        cap = capacity;
        count = 0;
    }
    
    int get(int key) {
        auto aim = m.find(key);
        if(aim == m.end())
            return -1;
        int ans = aim->second->second;
        queue.erase(aim->second);
        queue.push_front(make_pair(key, ans));
        aim->second = queue.begin();
        return ans;
    }
    
    void put(int key, int value) {
        auto aim = m.find(key);
        if(aim != m.end())
            queue.erase(aim->second);
        else if(count == cap) {
            m.erase(queue.back().first);
            queue.pop_back();
        }
        else
            count++;
        queue.push_front(make_pair(key, value));
        m[key] = queue.begin();
    }
};

/**
 * 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);
 */