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()
网友评论