美文网首页
leetcode 380. 常数时间插入、删除和获取随机元素

leetcode 380. 常数时间插入、删除和获取随机元素

作者: Burlong | 来源:发表于2022-03-17 22:15 被阅读0次

    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()));
        }
    }
    

    相关文章

      网友评论

          本文标题:leetcode 380. 常数时间插入、删除和获取随机元素

          本文链接:https://www.haomeiwen.com/subject/grpbdrtx.html