Leetcode 432. All O`one Data Structure (python)

题目

解法1：暴力O(N)

class AllOne:def __init__(self):"""Initialize your data structure here."""self.data = {
    }def inc(self, key: str) -> None:"""Inserts a new key <Key> with value 1. Or increments an existing key by 1."""if key in self.data:self.data[key] += 1else:self.data[key] = 1def dec(self, key: str) -> None:"""Decrements an existing key by 1. If Key's value is 1, remove it from the data structure."""if key in self.data:if self.data[key]>1:self.data[key] -= 1else:self.data.pop(key)def getMaxKey(self) -> str:"""Returns one of the keys with maximal value."""if not self.data:return ''max_value = 0max_key = Nonefor k,v in self.data.items():if v>max_value:max_value = vmax_key = kreturn max_keydef getMinKey(self) -> str:"""Returns one of the keys with Minimal value."""if not self.data:return ''min_value = float('inf')min_key = Nonefor k,v in self.data.items():if v<min_value:min_value = vmin_key = kreturn min_key

follow up:O(1)解法

对于四种操作都要是O(1)的话。首先对min和max操作，必须要以有序方式储存才能做到O(1)。而对于删除和加入操作要是O(1)，那就只有是链表才行。所以总结起来，我们需要维护一个有序的链表。下面手写了一个例子理解一下：

下面是解释：

• 主结构是一个链表A，节点的值代表key出现的count，升序排列。每个节点映射向另外一个链表B的开头，B里的节点储存相应的key
• hashmap1：key到node(key)的映射，保证我们以O(1)复杂度找到key所在的位置
• hashmap2：key到count，保证以O(1)复杂度知道当前给的key的count
• hashmap3：count节点到储存key的链表的头部
• hashmap4：count到count的节点，保证查找某个count节点为O(1)
  假设现在需要inc('a‘)，那么首先找到a对应的count，然后a对应的key node，查看count+1的节点是不是存在，如果存在则把a对应的key node移动到count+1对应的key 链表中去。不存在的话，新建count+1的node，并且同样需要移动key node。同时需要更新1，2，3，4 hashmap