Skip to content

381 Insert Delete GetRandom O(1) - Duplicates allowed

381. Insert Delete GetRandom O(1) - Duplicates allowed

题目: https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed/

难度 : Hard

一开始的想法是在380上面做简单的修改,比如用一个list来存每个数对应的location,但是这样remove会退化为O(N),然后看到:

  • 用 set 这个数据结构就可以贴近O(1)
  • 学了一个新的东西defaultdict, 相当于 D.get('key',defaultvalue)

这个defaultdict的好处就是添加的时候默认的值就是set,但是并不默认这个就存在

AC代码

class RandomizedCollection(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        import collections
        self.hashtable = collections.defaultdict(set)
        self.array = []

    def insert(self, val):
        """
        Inserts a value to the collection. Returns true if the collection did not already contain the specified element.
        :type val: int
        :rtype: bool
        """
        valin = val not in self.hashtable
        self.hashtable[val].add(len(self.array))
        self.array.append(val)
        return valin 

    def remove(self, val):
        """
        Removes a value from the collection. Returns true if the collection contained the specified element.
        :type val: int
        :rtype: bool
        """
        if val not in self.hashtable:
            return False
        else:
            if self.array[-1] == val:
                removeIdx = len(self.array) - 1
                self.hashtable[val].remove(removeIdx)
            else:
                # set pop remove arbitrary element
                removeIdx = self.hashtable[val].pop()
                self.array[removeIdx] = self.array[-1]
                self.hashtable[self.array[-1]].remove(len(self.array) - 1)
                self.hashtable[self.array[-1]].add(removeIdx)
            if len(self.hashtable[val]) == 0:
                del self.hashtable[val]
            del self.array[-1]
            return True


    def getRandom(self):
        """
        Get a random element from the collection.
        :rtype: int
        """
        import random
        return random.choice(self.array)

`



回到顶部