题目描述：
LeetCode 432. All O`one Data Structure
Implement a data structure supporting the following operations:
- Inc(Key) - Inserts a new key
with value 1. Or increments an existing key by 1. Key is guaranteed to be a non-empty string. - Dec(Key) - Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. Key is guaranteed to be a non-empty string. If the key does not exist, this function does nothing.
- GetMaxKey() - Returns one of the keys with maximal value. If no element exists, return an empty string
"". - GetMinKey() - Returns one of the keys with minimal value. If no element exists, return an empty string
"".
Challenge: Perform all these in O(1) time complexity.
题目大意：
设计数据结构支持下列操作：
- Inc(Key) - 新增值为1的key。如果key存在则将其值加1。key确保是非空字符串。
- Dec(Key) - 将已存在的key值减1。如果key值已经是1，则将其移除。如果key不存在，函数什么也不做。
- GetMaxKey() - 返回值最大的key中的1个。如果不存在，则返回空字符串""。
- GetMinKey() - 返回值最小的key中的1个。 如果不存在，则返回空字符串""。
挑战：所有操作用O(1)时间复杂度完成。
解题思路：
双向链表（Doubly Linked List） + 哈希表（Hash Table）
首先定义双向链表节点：KeyNode（Key节点）与ValueNode（Value节点）。
KeyNode中保存key（键），value（值），prev（前驱），next（后继） ValueNode中保存value（值）、prev（前驱）、next（后继）、first（指向第一个KeyNode）
在数据结构AllOne中维护如下属性：
keyDict：从key到KeyNode的映射 valueDict：从value到ValueNode的映射 head：指向最小的ValueNode tail：指向最大的ValueNode
整体数据结构设计如下图所示：
head --- ValueNode1 ---- ValueNode2 ---- ... ---- ValueNodeN --- tail
| | |
first first first
| | |
KeyNodeA KeyNodeE KeyNodeG
| | |
KeyNodeB KeyNodeF KeyNodeH
| |
KeyNodeC KeyNodeI
|
KeyNodeD
数据结构操作实现如下：
Inc(Key) / Dec(Key)：
首先从keyDict中找到对应的KeyNode，然后通过KeyNode的value值，从valueDict找到对应的ValueNode
如果ValueNode的next节点不等于value +/- 1，则在其右侧/左侧插入一个值为value +/- 1的新ValueNode节点
将KeyNode的value值+/-1后，从当前KeyNode链表转移到新的ValueNode对应的KeyNode链表
如果KeyNode移动之后，原来的ValueNode对应的KeyNode链表为空，则删除原来的ValueNode
在操作完毕后如果涉及到head和tail的变更，则更新head和tail
GetMaxKey() / GetMinKey()
直接返回head / tail对应ValueNode节点中first属性指向的KeyNode节点的key值。
Python代码：
class KeyNode(object):
def __init__(self, key, value):
self.key = key
self.value = value
self.prev = self.next = None
class ValueNode(object):
def __init__(self, value, prev, next):
self.value = value
self.prev = prev
self.next = next
self.first = None
class AllOne(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.keyDict = dict()
self.valueDict = dict()
self.head = self.tail = None
def inc(self, key):
"""
Inserts a new key <Key> with value 1. Or increments an existing key by 1.
:type key: str
:rtype: void
"""
if key in self.keyDict:
keyNode = self.keyDict[key]
valueNode = self.valueDict[keyNode.value]
nextValueNode = valueNode.next
keyNode.value += 1
if nextValueNode is None or nextValueNode.value > keyNode.value:
nextValueNode = self.insertValueNodeAfter(keyNode.value, valueNode)
if self.tail == valueNode:
self.tail = nextValueNode
self.unlinkKey(keyNode, valueNode)
self.linkKey(keyNode, nextValueNode)
else:
keyNode = self.keyDict[key] = KeyNode(key, 1)
valueNode = self.valueDict.get(1)
if valueNode is None:
valueNode = self.valueDict[1] = ValueNode(1, None, self.head)
if self.head:
self.head.prev = valueNode
self.head = valueNode
if self.tail is None:
self.tail = valueNode
self.linkKey(keyNode, valueNode)
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
"""
keyNode = self.keyDict.get(key)
if keyNode is None: return
valueNode = self.valueDict[keyNode.value]
if keyNode.value > 1:
prevValueNode = valueNode.prev
keyNode.value -= 1
if prevValueNode is None or prevValueNode.value < keyNode.value:
prevValueNode = self.insertValueNodeBefore(keyNode.value, valueNode)
if self.head == valueNode:
self.head = prevValueNode
self.unlinkKey(keyNode, valueNode)
self.linkKey(keyNode, prevValueNode)
else:
self.unlinkKey(keyNode, valueNode)
del self.keyDict[key]
def getMaxKey(self):
"""
Returns one of the keys with maximal value.
:rtype: str
"""
return self.tail.first.key if self.tail else ''
def getMinKey(self):
"""
Returns one of the keys with Minimal value.
:rtype: str
"""
return self.head.first.key if self.head else ''
def delValueNode(self, valueNode):
"""
Delete valueNode.
:rtype: void
"""
prev, next = valueNode.prev, valueNode.next
if prev: prev.next = next
if next: next.prev = prev
if self.head == valueNode: self.head = next
if self.tail == valueNode: self.tail = prev
del self.valueDict[valueNode.value]
def insertValueNodeAfter(self, value, node):
"""
Insert a new ValueNode(value) after node.
:rtype: ValueNode
"""
newNode = ValueNode(value, node, node.next)
self.valueDict[value] = newNode
if node.next: node.next.prev = newNode
else: self.tail = newNode
node.next = newNode
return newNode
def insertValueNodeBefore(self, value, node):
"""
Insert a new ValueNode(value) before node.
:rtype: ValueNode
"""
newNode = ValueNode(value, node.prev, node)
self.valueDict[value] = newNode
if node.prev: node.prev.next = newNode
else: self.head = newNode
node.prev = newNode
return newNode
def unlinkKey(self, keyNode, valueNode):
"""
Unlink keyNode from valueNode
:rtype: void
"""
next, prev = keyNode.next, keyNode.prev
if prev: prev.next = next
if next: next.prev = prev
if valueNode.first == keyNode: valueNode.first = next
if valueNode.first is None: self.delValueNode(valueNode)
def linkKey(self, keyNode, valueNode):
"""
Link keyNode to valueNode
:rtype: void
"""
firstKeyNode = valueNode.first
keyNode.prev = None
keyNode.next = firstKeyNode
if firstKeyNode: firstKeyNode.prev = keyNode
valueNode.first = keyNode
# 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()
本文链接：http://bookshadow.com/weblog/2016/10/18/leetcode-all-oone-data-structure/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。
捐赠书影博客
