Python LeetCode-432. 全 O(1) 的数据结

1.题目

实现一个数据结构支持以下操作：

• Inc(key) - 插入一个新的值为 1 的 key。或者使一个存在的 key 增加一，保证 key 不为空字符串。
• Dec(key) - 如果这个 key 的值是 1，那么把他从数据结构中移除掉。否者使一个存在的 key 值减一。如果这个 key 不存在，这个- 函数不做任何事情。key 保证不为空字符串。
• GetMaxKey() - 返回 key 中值最大的任意一个。如果没有元素存在，返回一个空字符串""。
• GetMinKey() - 返回 key 中值最小的任意一个。如果没有元素存在，返回一个空字符串""。

挑战：以 O(1) 的时间复杂度实现所有操作。

2.分析

• 代码很简单，但是在getMaxKey和getMinKey并没有实现O(1)级别的操作
• 有一个知识点：float('inf') 代表的是无穷大的数 +∞

3.解决

• 目前网上测试速度最快的写法

class AllOne(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.mydict = {}
        

    def inc(self, key):
        """
        Inserts a new key <Key> with value 1. Or increments an existing key by 1.
        :type key: str
        :rtype: None
        """
        if key not in self.mydict:
            self.mydict[key] = 1
        else:
            self.mydict[key] += 1
            

    def dec(self, key):
        """
        Decrements an existing key by 1. If Key's value is 1, remove it from the data structure.
        :type key: str
        :rtype: None
        """
        if key not in self.mydict:
            return
        elif self.mydict[key] == 1:
            del self.mydict[key]
        else:
            self.mydict[key] -= 1
        
    def getMaxKey(self):
        """
        Returns one of the keys with maximal value.
        :rtype: str
        """
        maxkey = ""
        self.mydict[maxkey] = 0
        for key in self.mydict.keys():
            if self.mydict[key] > self.mydict[maxkey]:
                maxkey = key  
        return maxkey
    
    def getMinKey(self):
        """
        Returns one of the keys with Minimal value.
        :rtype: str
        """
        minkey = ""
        self.mydict[minkey] = float('inf')  # float('inf') 代表的是无穷大的数 +∞
        for key in self.mydict.keys():
            if self.mydict[key] < self.mydict[minkey]:
                minkey = key  
        return minkey


# Your AllOne object will be instantiated and called as such:
# obj = AllOne()
# obj.inc(key)
# obj.dec(key)
# param_3 = obj.getMaxKey()
# param_4 = obj.getMinKey()

• 实现全O(1)的写法
  思路引用来自此处
  采用了双向链表来保存顺序

class Node:
    """
    定义双向链表的节点 双向链表用于按顺序存储(key,value)
    """

    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None


class AllOne:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.numDict = dict()  # 用于存储key与双向链表中node(key,node)映射关系
        self.head = Node("", -1)  # 头节点 存储最小值
        self.tail = Node("", -1)  # 尾节点 存储最大值
        # 初始化双向链表
        self.tail.prev = self.head
        self.head.next = self.tail

    def inc(self, key):
        """
        Inserts a new key <Key> with value 1. Or increments an existing key by 1.
        :type key: str
        :rtype: void
        """
        # 新增key,插入到numDict中,并放置在双向链表head->next
        if key not in self.numDict:
            insNode = Node(key, 1)  # 初始化新增节点
            self.numDict[key] = insNode  # 将这个节点放置到我们的字典当中
            insNode.next = self.head.next  # 第一步：进行双向链表拼接  这一步是断开head和下一个节点的连接
            self.head.next.prev = insNode  # 拼接第二步
            self.head.next = insNode  # 第三步
            insNode.prev = self.head  # 第四步
        else:
            # 存量key
            curNode = self.numDict[key]
            curNode.value += 1
            # 通过交换节点的方式保持双向链表有序
            while curNode.next != self.tail and curNode.value > curNode.next.value:
                prevNode = curNode.prev  # 保存前一个节点
                nextnextNode = curNode.next.next  # 保存curNode的next节点的next
                prevNode.next = curNode.next
                prevNode.next.prev = prevNode
                prevNode.next.next = curNode
                curNode.prev = prevNode.next
                curNode.next = nextnextNode
                nextnextNode.prev = curNode

    def dec(self, key):
        """
        Decrements an existing key by 1. If Key's value is 1, remove it from the data structure.
        :type key: str
        :rtype: void
        """
        if key not in self.numDict:
            return
        curNode = self.numDict[key]
        if curNode.value == 1:
            # 在双向链表中删除该节点
            prevNode = curNode.prev
            nextNode = curNode.next
            prevNode.next = nextNode
            nextNode.prev = prevNode
        else:
            # 该key对应的value减1 并通过交换节点的方式保持双向链表有序
            curNode.value -= 1
            while curNode.prev != self.head and curNode.value < curNode.prev.value:
                prepreNode = curNode.prev.prev
                nextNode = curNode.next
                nextNode.prev = curNode.prev
                curNode.prev.prev = curNode
                curNode.prev = prepreNode
                curNode.next = nextNode.prev
                nextNode.prev.next = nextNode
                prepreNode.next = curNode

    def getMaxKey(self):
        """
        Returns one of the keys with maximal value.
        :rtype: str
        """
        return self.tail.prev.key if self.tail.prev != self.head else ""

    def getMinKey(self):
        """
        Returns one of the keys with Minimal value.
        :rtype: str
        """
        return self.head.next.key if self.head.next != self.tail else ""

# Your AllOne object will be instantiated and called as such:
# obj = AllOne()
# obj.inc(key)
# obj.dec(key)
# param_3 = obj.getMaxKey()
# param_4 = obj.getMinKey()