leetcode 380. 常数时间插入、删除和获取随机元素
题目要求我们实现一个数据结构来支持插入、删除和获取随机元素的时间复杂度都在O(1)之内。
难点和突破点:
我们都知道数组通过索引下标进行访问是很快的,但插入、删除就不一样了,比如插入操作,需要在插入元素后,将插入位置后的所有元素都向后移动,以保证内存的紧凑、连续性,这需要O(n)的平均时间复杂度。仔细想想,这个平均复杂度里面,最优的复杂度是多少?
答案是O(1),就是操作数组尾部元素时,可以达到O(1)的时间复杂度,对于插入尾部的操作,因为插入后本身就是数组的最后一个元素,所以不需要再移动后面的元素,而对于删除操作亦是如此,删除后不需要再将后面元素向前移动。
既然知道了操作尾部可以得到最优的时间复杂度,那么我们要做的,就是想办法在每次的插入、删除操作时,都只操作数组尾部,以避免数据迁移;
抓住了这个特点,我们可以考虑用hash表来对val→index做一层映射:
1、对于插入操作,我们直接使用封装好的ArrayList.add(T t)方法(只要不触发扩容,那么该方法可以让每次插入操作都插入到数组的尾部,为O(1)的时间复杂度),同时我们把插入的元素以val→index(因为每次都是插入到最后,因此index就是数组尾部下标)的形式放入hash表中,后续删除操作需要用到;
2、对于删除操作,我们要做的,就是每次将数组尾部的元素lastVal与当前要删除的元素val的位置做一次调换(通过hash表找到val在数组中的索引下标),然后清空尾部,释放内存即可,做完这步后,还需要维护一下hash表,把目标元素占用的k-v对删除掉,同时更新lastVal在hash表中的索引映射。
3、对于获取随机元素,我们只需要在根据下标获取元素时,对size做一个random后作为下标,即可随机拿到一个元素。
代码如下:
public class RandomizedSet {
// 存储所有val
List<Integer> nums ;
// val->index哈希表,映射每个val在nums中的索引位置
Map<Integer, Integer> valToIndex;
Random random;
public RandomizedSet() {
nums = new ArrayList<>();
valToIndex = new HashMap<>();
random = new Random();
}
public boolean insert(int val) {
// 存在直接返回
if (valToIndex.containsKey(val)) {
return false;
}
// 直接添加到list中,并用hash表记录val在list中的下标
nums.add(val);
valToIndex.put(val, nums.size() - 1);
return true;
}
public boolean remove(int val) {
if (!valToIndex.containsKey(val)) {
return false;
}
// 1、找出val在nums中的索引
Integer valIdx = valToIndex.get(val);
// 2、取出nums尾部元素,替换val,并删除nums尾部(关键代码)
Integer lastVal = nums.get(nums.size() - 1);
nums.set(valIdx, lastVal);
nums.remove(nums.size() - 1);
// 3、更新索引hash表,并remove掉val占用的entry
valToIndex.put(lastVal, valIdx);
valToIndex.remove(val);
return true;
}
public int getRandom() {
return nums.get(random.nextInt(nums.size()));
}
}
网友评论