# Question

Formatted question description: https://leetcode.ca/all/381.html

 381. 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.

insert(val): Inserts an item val to the collection.
remove(val): Removes an item val from the collection if present.
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:

// Init an empty collection.
RandomizedCollection collection = new RandomizedCollection();

// Inserts 1 to the collection. Returns true as the collection did not contain 1.
collection.insert(1);

// Inserts another 1 to the collection. Returns false as the collection contained 1. Collection now contains [1,1].
collection.insert(1);

// Inserts 2 to the collection, returns true. Collection now contains [1,1,2].
collection.insert(2);

// getRandom should return 1 with the probability 2/3, and returns 2 with the probability 1/3.
collection.getRandom();

// Removes 1 from the collection, returns true. Collection now contains [1,2].
collection.remove(1);

// getRandom should return 1 and 2 both equally likely.
collection.getRandom();

@tag-array



# Algorithm

For the insert() function, we add the position of the number to be inserted in nums to the end of the m[val] array, and then add val to the end of the array nums. We judge whether there is a duplication as long as the m[val] array has only one value of val just added or there are multiple values.

The remove() function is the difficulty of this problem. First, let’s see if there is a val in the HashMap, and if not, return false directly. Then we take the tail element of nums, and update the last position in the position array of the tail element HashMap to the tail element of m[val], so that we can delete the tail element of m[val]. If m[val] ] There is only one element, then we delete this mapping directly. Then delete the tail element in the nums array and assign the tail element to the position of val.

• Note that we need to use a heap instead of a normal vector array when building the mapping of HashMap

We use the priority queue to automatically sort all the coordinates of the same number, and move out the coordinates of the largest position each time.

Java