#381

Insert Delete GetRandom O(1) - Duplicates allowed

master · 1805 · lc hard +32 · 36.4% accepted · 2,421 likes · top 14%

Description

Build a multiset data structure that permits duplicate values, supporting insert, remove, and random retrieval each in average O(1) time.

Implement the RandomizedCollection class:

- RandomizedCollection() Constructs an empty collection.

- bool insert(int val) Adds one copy of val (duplicates allowed); returns true if val was not previously present, false if it was.

- bool remove(int val) Removes one copy of val if any exist; returns true if a copy was found and removed, false otherwise.

- int getRandom() Returns a random element with probability proportional to how many times it appears (the collection is guaranteed non-empty when called).

Each function must work on average O(1) time complexity.

Example 1:

Input

["RandomizedCollection", "insert", "insert", "insert", "getRandom", "remove", "getRandom"]

[[], [1], [1], [2], [], [1], []]

Output

[null, true, false, true, 2, true, 1]

Example 2:

Explanation

RandomizedCollection randomizedCollection = new RandomizedCollection();

randomizedCollection.insert(1); // return true since the collection does not contain 1.

// Inserts 1 into the collection.

randomizedCollection.insert(1); // return false since the collection contains 1.

// Inserts another 1 into the collection. Collection now contains [1,1].

randomizedCollection.insert(2); // return true since the collection does not contain 2.

// Inserts 2 into the collection. Collection now contains [1,1,2].

randomizedCollection.getRandom(); // getRandom should:

// - return 1 with probability 2/3, or

// - return 2 with probability 1/3.

randomizedCollection.remove(1); // return true since the collection contains 1.

// Removes 1 from the collection. Collection now contains [1,2].

randomizedCollection.getRandom(); // getRandom should return 1 or 2, both equally likely.

Code

class RandomizedCollection:

    def __init__(self):
        

    def insert(self, val: int) -> bool:
        

    def remove(self, val: int) -> bool:
        

    def getRandom(self) -> int:
        


# Your RandomizedCollection object will be instantiated and called as such:
# obj = RandomizedCollection()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()

class RandomizedCollection:

    def __init__(self):
        

    def insert(self, val: int) -> bool:
        

    def remove(self, val: int) -> bool:
        

    def getRandom(self) -> int:
        


# Your RandomizedCollection object will be instantiated and called as such:
# obj = RandomizedCollection()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()