leetcode--380. O (1) time insertion, deletion and acquisition of random elements

• subject ： Realization RandomizedSet class ：

1. RandomizedSet() initialization RandomizedSet object
2. bool insert(int val) When element val When there is no , Insert the item into the collection , And back to true ; otherwise , return false .
3. bool remove(int val) When element val In existence , Remove the item from the collection , And back to true ; otherwise , return false .
4. int getRandom() Random return of an item in an existing collection （ The test case guarantees that there is at least one element in the collection when this method is called ）. Every element should have Same probability Returned .
   You must implement all the functions of the class , And satisfy the of each function Average The time complexity is O(1) .¹

• Example ：

# Example 1
 Input 
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
 Output 
[null, true, false, true, 2, true, false, 2]

 explain 
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); //  Insert into collection  1 . return  true  Express  1  Successfully inserted .
randomizedSet.remove(2); //  return  false , Indicates that the collection does not exist  2 .
randomizedSet.insert(2); //  Insert into collection  2 . return  true . The collection now contains  [1,2] .
randomizedSet.getRandom(); // getRandom  Should return at random  1  or  2 .
randomizedSet.remove(1); //  Remove from collection  1 , return  true . The collection now contains  [2] .
randomizedSet.insert(2); // 2  Already in collection , So back  false .
randomizedSet.getRandom(); //  because  2  Is the only number in the set ,getRandom  Always returns  2 .

• Tips ：

1. -231 <= val <= 231 - 1
2. Call at most insert、remove and getRandom function 2 * 105 Time
3. Calling getRandom When the method is used , In the data structure There is at least one Elements .

• Solution 1 – list ：

class RandomizedSet:
    def __init__(self):
        self.element = []
        self.index = 0

    def insert(self, val):
        if val in self.element:
            return False
        else:
            self.element.append(val)
            return True

    def remove(self, val):
        if val in self.element:
            self.element.remove(val)
            return True
        else:
            return False

    def getRandom(self):
        return random.choice(self.element)

• Solution 2 – aggregate ：

class RandomizedSet:
    def __init__(self):
        self.element = []
        self.index = 0

    def insert(self, val):
        if val in self.element:
            return False
        else:
            self.element.append(val)
            return True

    def remove(self, val):
        if val in self.element:
            self.element.remove(val)
            return True
        else:
            return False

    def getRandom(self):
        return random.choice(self.element)

• summary ： There is a mistake to pay attention to , Not clear about the elements defined in the class , If you want this element to change as the class changes , Just define it into the initialization method , namely __init__.

---

1. source ： Power button （LeetCode）
   link ：https://leetcode-cn.com/problems/insert-delete-getrandom-o1 ︎