146. LRU 缓存

参考146. LRU 缓存。

题目

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类：

• LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存

• int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。

• void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

解题思路

• 哈希表+双向链表：链表的处理细节比较多,需要注意链表指针的变换,使用哈希表作为存储数据结构,要想实现put操作O(1)时间复杂度,需要用双向链表结构存储哈希表里面的pre和next节点,链表头指向最久未使用的节点,最近使用的节点放在末尾使用head和tail两个节点记录。

哈希表+双向链表

class LRUCache {

    HashMap<Integer,Node> hm = new HashMap<>();
    Node head = null,tail = null;
    int capacity = 0,len = 0;
    public LRUCache(int capacity) {
        this.capacity = capacity;
    }
    
    public int get(int key) {
        if(!hm.containsKey(key)) return -1;
        Node node = hm.get(key);
        if(tail != node) {
            Node pre = node.pre,next = node.next;
            tail.next = node;
            node.pre = tail;
            tail = node;
            if(pre != null){
                pre.next = next;
                next.pre = pre;
            }
            else {
                head = next;
                head.pre = null;
            }
        }
        return node.value;
    }
    
    public void put(int key, int value) {
        if(hm.containsKey(key)){
            Node cur = hm.get(key);
            cur.value = value;
            if(tail != cur){
                Node pre = cur.pre,next = cur.next;
                tail.next = cur;
                cur.pre = tail;
                tail = cur;
                if(pre != null){
                    pre.next = next;
                    next.pre = pre;
                }
                else{
                    head = next;
                    head.pre = null;
                } 
            }
        } 
        else {
            Node cur = null;
            if(len == capacity) { //满了删掉最久未使用的key
                if(head != null) {
                    hm.remove(head.key);
                    Node hnext = head.next;
                    head = hnext;
                    if(head != null)head.pre = null;
                    if(head == tail) tail = null;
                }
                cur = new Node(key,value);
                hm.put(key,cur);//先删除后添加防止内存不足
            }else {
                cur = new Node(key,value);
                hm.put(key,cur);
                len += 1;
                if(len == 1) {
                    head = cur;
                    tail = cur;
                }
            } 
            if(tail != hm.get(key)){
                if(tail != null) tail.next = cur;
                cur.pre = tail;
                tail = cur;
                if(capacity == 1) head = tail;
            }
        }
        
    }

    class Node{
        int key,value;
        Node pre,next;
        Node(int key,int value){
            this.key = key;
            this.value = value;
        }
    }
}

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

复杂度分析

• 时间复杂度：O(1)，哈希表的存储和访问都是O(1)。
• 空间复杂度：O(k)，k为capacity即LRU`容量.