题目要求
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();
设计一个数据结构，支持能够在 O(1)的时间内完成对数字的插入，删除和获取随机数的操作，允许插入重复的数字，同时要求每个数字被随机获取的概率和该数字当前在数据结构中的个数成正比。
强烈建议先看一下这个问题的基础版本，传送门在这里。
思路和代码
遵循之前基础版本的思路，当解决这种问题的时候我们会用数组和 hashmap 来做位置的存储，从而更新的时候无需检索。但是在这题的情境下，存在一个问题，举个例子：假如现在插入 1,2,3,3,4,3,3 此时的 map 中应当是如下：1:[0] 2:[1] 3:[2,3,5,6] 4:[4]我们先执行删除 1，按照之前的规则，我们会删除数组中最后一个元素，并将其值移动到这个位置上 map 应当被更新为 2:[1] 3:[2,3,5,0] 4:[4]接着我们再删除 2，此时虽然最后一个元素还是 3，但是这个 3 在位置数组中的位置却是需要 O(n)的时间来查询的，这就违反了 O(1)的删除时间复杂度。
网上有一些 java 实现采用 OrderSet 来解决，这是不合理的。因为有序堆本质上底层是一个最大堆或最小堆，它的插入和删除操作都需要 O(lgn)的时间复杂度来完成
这里我们采用的方式是继续冗余，即我们在插入每一个元素的时候，同时记录该元素在下标数组中的位置，举个例子：先插入 1，则 map 的值为 [1:[0]]，list 的值为[[1,0]] 此处的 0 代表 1 这个值在下标数组[0] 中位于第 0 个位置上。在插入 2，则 map 的值为 [1:[0], 2:[1]], list 的值为[[1,0],[2,0]] 再插入 1，此时 map=[1:[0, 2], 2:[1], list 的值为 [[1,0],[2,0],[1,1]] 此时删除 2，同理，我们还是会将数组中最后一个元素的值替换在删除掉元素的位置，此处我们从 map 中得出 2 最后一次在数组中出现的下标为 1，我们需要将最后位置上的 1 替换掉当前 2 的值，之后我们还能从数组中得知，1 这个数字它对应的位置下标的索引为 2，因此我们再将 map[1]中 map[1][2]的值替换为 2 所在的新的位置，即 1。此时的 map=[1:[0, 1], 2:[] list=[[1,0], [1,1]]
代码如下：
public class InsertDeleteGetRandomDuplicatesallowed_381 {
private List<Pair> list;
private Map<Integer, List<Integer>> index;
/** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
public InsertDeleteGetRandomDuplicatesallowed_381() {
list = new ArrayList<>();
index = new HashMap<>();
}
public boolean insert(int val) {
boolean contains = true;
if(!index.containsKey(val) || index.get(val).isEmpty()) {
contains = false;
}
List<Integer> tmp = index.getOrDefault(val, new ArrayList<>());
tmp.add(list.size());
index.put(val, tmp);
list.add(new Pair(val, tmp.size()-1));
return !contains;
}
/** Removes a value from the collection. Returns true if the collection contained the specified element. */
public boolean remove(int val) {
if(!index.containsKey(val) || index.get(val).isEmpty()) {
return false;
}
List<Integer> tmp = index.get(val);
int position = tmp.remove(tmp.size()-1);
if(position != list.size()-1) {
Pair lastPair = list.get(list.size()-1);
int lastValue = lastPair.value;
List<Integer> lastValuePositions = index.get(lastValue);
lastValuePositions.set(lastPair.position, position);
list.set(position, lastPair);
}
list.remove(list.size()-1);
return true;
}
/** Get a random element from the collection. */
public int getRandom() {
int position = (int)Math.floor((Math.random() * list.size()));
return list.get(position).value;
}
public static class Pair{
int value;
int position;
public Pair(int value, int position) {
this.value = value;
this.position = position;
}
}
}