Implement a data structure supporting the following operations:

LeetCode 432. All Oone Data Structure

Description

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) – If Key’s value is 1, remove it from the data structure. Otherwise decrements an existing key by 1. If the key does not exist, this function does nothing. Key is guaranteed to be a non-empty string.
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 增加一,保证 key 不为空字符串。
Dec(key) – 如果这个 key 的值是 1,那么把他从数据结构中移除掉。否者使一个存在的 key 值减一。如果这个 key 不存在,这个函数不做任何事情。key 保证不为空字符串。
GetMaxKey() – 返回 key 中值最大的任意一个。如果没有元素存在,返回一个空字符串””。
GetMinKey() – 返回 key 中值最小的任意一个。如果没有元素存在,返回一个空字符串””。
挑战:以 O(1) 的时间复杂度实现所有操作。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/all-oone-data-structure
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


思路

  • 使用 Hash 表 + 链表来实现全部 O(1) 的操作。
  • Hash 表指向链表节点,每个节点存储哪些 key 指向了自己,并存储自己的 value,前一个节点 before,后一个节点 before。
  • 对于每一节点:keys 为 set,存储有哪些 key 指向了自己,val 是当前节点的值,before 指向前一个节点,after 指向后一个节点。
  • 参考这个
    ……
class Block(object):
    def __init__(self, val=0):
        self.val = val
        self.keys = set()
        self.before = None
        self.after = None

    def remove(self):
        self.before.after = self.after
        self.after.before = self.before
        self.before, self.after = None, None

    def insert_after(self, new_block):
        old_after = self.after
        self.after = new_block
        new_block.before = self
        new_block.after = old_after
        old_after.before = new_block


class AllOne(object):
    def __init__(self):
        self.begin = Block()  # sentinel
        self.end = Block()  # sentinel
        self.begin.after = self.end
        self.end.before = self.begin
        self.mapping = {}  # key to block

    def inc(self, key):
        if not key in self.mapping:  # find current block and remove key
            current_block = self.begin
        else:
            current_block = self.mapping[key]
            current_block.keys.remove(key)

        if current_block.val + 1 != current_block.after.val:  # insert new block
            new_block = Block(current_block.val + 1)
            current_block.insert_after(new_block)
        else:
            new_block = current_block.after

        new_block.keys.add(key)  # update new_block
        self.mapping[key] = new_block  # ... and mapping of key to new_block

        if not current_block.keys and current_block.val != 0:  # delete current block if not seninel
            current_block.remove()

    def dec(self, key):
        if not key in self.mapping:
            return

        current_block = self.mapping[key]
        del self.mapping[key]  # could use self.mapping.pop(key)
        current_block.keys.remove(key)

        if current_block.val != 1:
            if current_block.val - 1 != current_block.before.val:  # insert new block
                new_block = Block(current_block.val - 1)
                current_block.before.insert_after(new_block)
            else:
                new_block = current_block.before
            new_block.keys.add(key)
            self.mapping[key] = new_block

        if not current_block.keys:  # delete current block
            current_block.remove()

    def getMaxKey(self):
        if self.end.before.val == 0:
            return ""
        key = self.end.before.keys.pop()  # pop and add back to get arbitrary (but not random) element
        self.end.before.keys.add(key)
        return key

    def getMinKey(self):
        if self.begin.after.val == 0:
            return ""
        key = self.begin.after.keys.pop()
        self.begin.after.keys.add(key)
        return key
Posted in LeetCode.

花若盛開,蝴蝶自來. 分享学习,每天进步一点点

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.