0%

### 题目描述

Implement the `RandomizedSet` class:

• `RandomizedSet()` Initializes the `RandomizedSet` object.
• `bool insert(int val)` Inserts an item `val` into the multiset if not present. Returns `true` if the item was not present, `false` otherwise.
• `bool remove(int val)` Removes an item `val` from the multiset if present. Returns `true` if the item was present, `false` otherwise.
• `int getRandom()` Returns a random element from the current multiset of elements (it’s guaranteed that at least one element exists when this method is called). Each element must have the linear probability to the number of same values the multiset contains..

You must implement the functions of the class such that each function works in average `O(1)` time complexity.

### 例子

Input:
`["RandomizedCollection", "insert", "insert", "insert", "getRandom", "remove", "getRandom"]`
`[[], [1], [1], [2], [], [1], []]`
Output:`[null, true, false, true, 2, true, 1]`
Explanation:
`RandomizedCollection randomizedCollection = new RandomizedCollection();`
`randomizedCollection.insert(1); // return True. Inserts 1 to the collection. Returns true as the collection did not contain 1.`
`randomizedCollection.insert(1); // return False. Inserts another 1 to the collection. Returns false as the collection contained 1. Collection now contains [1,1].`
`randomizedCollection.insert(2); // return True. Inserts 2 to the collection, returns true. Collection now contains [1,1,2].`
`randomizedCollection.getRandom(); // getRandom should return 1 with the probability 2/3, and returns 2 with the probability 1/3.`
`randomizedCollection.remove(1); // return True. Removes 1 from the collection, returns true. Collection now contains [1,2].`
`randomizedCollection.getRandom(); // getRandom should return 1 and 2 both equally likely.`

### Constraints

• `-2^31 <= val <= 2^31 - 1`
• At most `2 * 10^5` calls will be made to `insert`, `remove`, and `getRandom`.
• There will be at least one element in the data structure when getRandom is called.

### 解题思路

[Leetcode]380. Insert Delete GetRandom O(1)(C++) 的进阶版本，要求数组中可以存在重复数字，因此我们做法类似，但是在存储数组的下标方式需要做出一些调整。从值-值改为值-集合，使得可以存储多个下标。插入和返回随机元素的过程基本不用改变，而在去除元素时，要注意哈希表中值更新的顺序，具体参考代码如下：

• 时间复杂度: `O(1)`
• 空间复杂度: `O(n)`

GitHub 代码同步地址： 381.InsertDeleteGetRandomO1DuplicatesAllowed.cpp

GitHub: Leetcode-C++-Solution