[LeetCode]All O`one Data Structure

题目描述:

LeetCode 432. All O`one Data Structure

Implement a data structure supporting the following operations:

  1. 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.
  2. 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.
  3. GetMaxKey() - Returns one of the keys with maximal value. If no element exists, return an empty string "".
  4. 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.

题目大意:

设计数据结构支持下列操作:

  1. Inc(Key) - 新增值为1的key。如果key存在则将其值加1。key确保是非空字符串。
  2. Dec(Key) - 将已存在的key值减1。如果key值已经是1,则将其移除。如果key不存在,函数什么也不做。
  3. GetMaxKey() - 返回值最大的key中的1个。如果不存在,则返回空字符串""。
  4. 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/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码