Code

Solution of problem 380 is showed below. You can also find it here.

Solution

The hard point of the problem is the random operation. The insert and remove operator can be easily done by dictionary structure, like std:map or std:unordered_map. To implement the random operator, array-like stucture is necessary. But it is hard to add or delete in O(1) time. To combine them, we can save the data in a array-like structure and save their position in a dictionary structure. To remove a element, we can find the position from the dictionary structure and swap it with the last one so that we can remove it in both structure in O(1) time.

VAluable Method

To recall the problem, it is not that hard. But it took me long time on the random operator. It’s weird. When inserting or deleting elements in a heap, you add an element to the last position or swap the top element with the last element, and then follow the heap rules to adjust it. Here, it uses the same method.