Skip to content

380 Insert Delete GetRandom O(1)

380. Insert Delete GetRandom O(1)

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

难度 : Hard

我的naive TLE代码,关键还是在想这个getRandom,这就不是O(1)的:

class RandomizedSet(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.container = {}


    def insert(self, val):
        """
        Inserts a value to the set. Returns true if the set did not already contain the specified element.
        :type val: int
        :rtype: bool
        """
        # 1 stands for present
        if val in self.container and self.container[val] == 1:
            return False
        else:
            self.container[val] = 1
            return True


    def remove(self, val):
        """
        Removes a value from the set. Returns true if the set contained the specified element.
        :type val: int
        :rtype: bool
        """
        if self.container.get(val,0) == 1:
            self.container[val] = 0
            return True
        else:
            return False



    def getRandom(self):
        """
        Get a random element from the set.
        :rtype: int
        """
        import random
        keys = self.container.keys()
        rd = random.randint(0, len(keys) - 1)
        if self.container[keys[rd]] == 1:
            return keys[rd]
        elif self.container.get(keys[rd],0) == 0:
            return self.getRandom()

也是有stackoverflow问题界面的题目

Consider a data structure composed of a hashtable H and an array A. The hashtable keys are the elements in the data structure, and the values are their positions in the array.

1.insert(value): append the value to array and let i be its index in A. Set H[value]=i.

2.remove(value): We are going to replace the cell that contains value in A with the last element in A. let d be the last element in the array A at index m. let i be H[value], the index in the array of the value to be removed. Set A[i]=d, H[d]=i, decrease the size of the array by one, and remove value from H.

3.contains(value): return H.contains(value)

4.getRandomElement(): let r=random(current size of A). return A[r].

since the array needs to auto-increase in size, it's going to be amortize O(1) to add an element, but I guess that's OK.

按照以答案AC代码

class RandomizedSet(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.hashtable = {}
        self.array = []
        self.arraySize = 0

    def insert(self, val):
        """
        Inserts a value to the set. Returns true if the set did not already contain the specified element.
        :type val: int
        :rtype: bool
        """
        # already in the set
        if val in self.hashtable:
            return False
        else:
            self.hashtable[val] = self.arraySize
            self.array.append(val)
            self.arraySize += 1
            return True


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



    def getRandom(self):
        """
        Get a random element from the set.
        :rtype: int
        """
        import random
        rd = random.randint(0, self.arraySize-1)
        return self.array[rd]

最后getRandom也可以写成:

return random.choice(self.array)



回到顶部