LeetCode 380 - Insert Delete GetRandom O(1)

作者 QIFAN 日期 2017-01-31
LeetCode 380 - Insert Delete GetRandom O(1)

原题链接: 380. Insert Delete GetRandom O(1)


题干

设计一个数据结构,使其能用 $O(1)$ 实现:
insert(val)
remove(val)
getRandom 任意返回元素,每个元素返回的概率要相同。

思路

插入 O(1) 是 LinkedList ,ArrayList。
删除特定元素,先找到,再删除,LinkedList、 map 都可以。
getRandom ,也是要去任意的定位,应该是数组了。
加起来感觉像是要自己用数组实现一个 hashmap 。但是这样 random 不能实现。

啊又没有想出方法,卡点在于处理删除后产生的 gap 和 index 的变化。

看了别人的解法,其实就是删除哪里不会产生 gap ,头和尾,而不会对 index 造成影响的就是 尾部,所以只要尾的节点来填充 gap 就好了。使用 HashMap + ArrayList 。

public class RandomizedSet {
List<Integer> list;
Map<Integer, Integer> map;
Random rand;
/** Initialize your data structure here. */
public RandomizedSet() {
list = new ArrayList<>();
map = new HashMap<>();
rand = new Random();
}
/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
public boolean insert(int val) {
if (map.containsKey(val)) {
return false;
}
map.put(val, list.size());
list.add(val);
return true;
}
/** Removes a value from the set. Returns true if the set contained the specified element. */
public boolean remove(int val) {
if (!map.containsKey(val)) {
return false;
}
// 如果不是最后一个,和最后一个位置交换
if (map.get(val) != list.size() - 1) {
int last = list.get(list.size() - 1);
list.set(map.get(val), last);
map.put(last, map.get(val));
}
map.remove(val);
list.remove(list.size() - 1);
return true;
}
/** Get a random element from the set. */
public int getRandom() {
return list.get(rand.nextInt(list.size()));
}
}