题解 | #排序#

题解中大部分的时间复杂度都不满足题目中要求的O（1）。
满足时间复杂度的算法：

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.next = None
        self.pre = None
    def __str__(self):
        return '%s %s' %(self.key,self.value) 
class Solution:
    def __init__(self,max_size = 0):
        self.max_size = max_size
        self.size = 0
        self.head = None
        self.tail = None

    def set(self, key, value):
        if not self.dic: #链表为空
            temp =  Node(key, value) #创建新节点并将头指针指向新节点
            self.head = temp
            self.tail = temp #将尾指针也指向新节点
            self.dic[key] = self.head #在字典中存储key键及相应的节点
            self.size += 1
        elif key not in self.dic: #key值不在链表中
            temp = Node(key, value) #创建新节点
            temp.next =self.head  #将新节点的尾指针指向之前的头节点
            self.head.pre = temp #将原先头节点的头指针指向新创建的节点
            self.head =temp #将头指针指向新节点
            self.dic[key] = self.head #在字典中存储key键及相应的节点
            self.size += 1

        #key值在链表中，意为更新key对应的value
        elif self.head.key != key and self.tail != key: #更新的节点前后都有节点
            temp = self.dic[key] #从字典中获取待更新节点
            temp.value = value #更新待更新节点的值
            temp.pre.next = temp.next
            temp.next.pre = temp.pre
            temp.next = self.head
            self.head.pre = temp
            self.head = temp
            #self.dic[key].value = temp
        elif self.head == key: #更新的节点为头节点
            self.head.value = value
        elif self.tail == key and self.head != key: #更新的节点为尾节点
            self.tail.value = value
            self.tail.next = self.head
            self.head.pre = self.tail
            self.head = self.tail
            self.tail = self.tail.pre
            self.tail.next =None
            self.head.pre = None

        if self.size > self.max_size:
            temp = self.tail.key #暂存key值以便后续删除字典中对应的元素
            self.tail = self.tail.pre #尾指针前移
            self.tail.next.pre = None
            self.tail.next = None
            del self.dic[temp]
            self.size -= 1

    def get(self, key):
        if key not in self.dic: #没有搜索的节点
            return -1
        if self.head.key == key: #搜所得节点为头节点
            return self.head.value
        if self.tail.key == key: #搜索的节点为尾节点
            self.tail.next = self.head
            self.head.pre = self.tail
            self.head = self.tail
            self.tail = self.tail.pre
            self.tail.next = None
            self.head.pre = None
            return self.head.value
        else:
            temp = self.dic[key]
            temp.pre.next = temp.next
            temp.next.pre = temp.pre
            temp.next = self.head
            self.head.pre = temp
            self.head = temp
            return self.head.value

    def LRU(self,operators, k):
        self.max_size = k
        ret = []
        for opt in operators:
            if opt[0] == 1:
                self.set(opt[1], opt[2])
            elif opt[0] == 2:
                ret.append(self.get(opt[1]))
        return ret