Description
Design a data structure that supports all following operations in average O(1) time.
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
Example 1:
Input:
insert(1)
insert(1)
insert(2)
getRandom()
remove(1)
// 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();
Example 2:
Input:
insert(1)
insert(1)
getRandom()
remove(1)
思路：
和没有重复的那个题思路类似，但是因为允许有重复数字，所以hash_map中用List存储了所有一样val的index，注意函数defaultdict对于任何一个遍历到的val都会有一个默认的空set，所以再remove的时候要去判断self.index[val]是不是空，而不能用not in self.index。另外删除一个val的时候并没有真正的删除，而是将list中那个val替换成了None，所以在生成随机数的时候，要排除掉那些为None的值。
用 HashMap 存储 number to a list of indices in numbers array. 也就是说，把某个数在数组中出现的所有的位置用 List 的形式存储下来
这样子的话，删除一个数的时候，就是从这个 list 里随便拿走一个数（比如最后一个数）
但是还需要解决的问题是，原来的算法中，删除一个数的时候，需要拿 number array 的最后个位置的数，来覆盖掉被删除的数。那这样原本在最后一个位置的数，他在 HashMap 里的记录就应该相应的变化。
但是，我们只能得到这个移动了的数是什么，而这个被移动过的数，可能出现在好多个位置上，去要从 HashMap 里得到的 indices 列表里，改掉那个 index=当前最后一个位置的下标。
所以这里的做法是，修改 number array，不只是存储 Number，同时存储，这个数在 HashMap 的 indices 列表中是第几个数。这样就能直接去改那个数的值了。否则还得 for 循环一次，就无法做到 O(1)
代码：
网友评论