leetcode Insert Delete GetRandom O(1) – Duplicates allowed

leetcode Insert Delete GetRandom O(1) – Duplicates allowed

Design a data structure that supports all following operations in average O(1) time.

Note: Duplicate elements are allowed.

1. insert(val): Inserts an item val to the collection.
2. remove(val): Removes an item val from the collection if present.
3. getRandom: Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the collection contains.

Example:

C++

Python

Leetcode , , , . permalink.

13 thoughts on “leetcode Insert Delete GetRandom O(1) – Duplicates allowed”

1. wei dai says:

SET 的REMOVE 明显不是 O(1)吧

self.index[last].remove(len(self.output))
这句话本质上和用个LIST来存 没什么区别

2. Tim says:

This is a great question and I saw that it has been asked by Uber and Google recently. I didn’t come up with the solution at the beginning. Btw, I also read a great analysis of the same problem at http://bit.ly/2bCPP47.

3. Jinkai Wang says:

looks like if we are using SET, the complexity won’t be O(1), that’s where I’m struggling with.

• That’s why the problem requires not the worst case time complexity, but average O(1) time.

4. guanglightman says:

The above algorithm maybe not safe (and also I doubt it’s correctness). I think everything inside the list index[val] should be maintained in ordered.

A simple example:
start from 3 4 5 6 1 2 1 2
and then remove 3 4 5 6 2 2
in the last step(remove 2), the code has accessed outbound memory.

• You are right. Thanks for pointing it out.
My solution is not correct because it is not maintain the index order.
If we keep the index order, use a heap or AVL tree or binary search or like Insertion sort, it will be right, but it is not O(1).
I doubt the problem has not O(1) solution.

• guanglightman says:

A randomized algorithm is listed below, You may find some explanation in comment part inside the code. Some issues may also remained.

Best,
Guang

• guanglightman says:

Also, FYI, the code cannot be displayed nicely in your blog comment area.

Best,
Guang

• Now, I use unordered_set instead of vector
Use a unordered_set can remove and insert O(1) time and we don’t need to maintain the order.

• guanglightman says:

Ooh, that’s a much simpler and smarter way!

• you can use html tag “pre” in my blog. ^ ^