380.线性时间时间插入、删除和获取随机元素

发表于： 分类于：
字数： 889 阅读：≈ 2分钟

🍅 380.线性时间时间插入、删除和获取随机元素

实现RandomizedSet 类：

  • RandomizedSet() 初始化 RandomizedSet 对象
  • bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
  • bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
  • int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。

你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。

思路

提示

  • -231 <= val <= 231 - 1
  • 最多调用 insert、remove 和 getRandom 函数 2 * 10^5 次
  • 在调用 getRandom 方法时，数据结构中 至少存在一个 元素。

基本思想

为了实现线性时间的插入和删除，需要知道最耗费时间的是什么，为了插入和删除，首先需要找到这个元素，找元素的过程就很消耗时间，于是将找元素的功能集成到哈希表中，这样找元素就可以在线性时间内完成，为了进一步减小插入和删除的时间复杂度，可以将元素存储到一个数组中，插入时直接在尾部插入，然后在哈希表中记录元素的值和元素的位置，删除时先在哈希表中找到元素的位置，然后让数组的默认元素覆盖待删除的元素即可

哈希表负责记录元素的位置，数组负责存储元素，这样插入和删除都很快

执行流程

  1. 初始化哈希表存储元素的位置，键代表元素的内容，值代表元素在数组中存储的位置
  2. 初始化数组存储元素的内容，使用一个下标记录当前有效元素的最后位置，因为提示中说最多调用 insert、remove 和 getRandom 函数 2 * 10^5 次，所以数组最大就是200000
  3. 插入时先记录元素的位置，再插入
  4. 删除时先获取元素的位置，再删除，删除的时候直接使用最后一个位置的元素覆盖待删除元素，然后更新哈希表中元素的位置，最后更新数组的长度即可

代码

根据以上分析，得出以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class RandomizedSet {
    private Map<Integer,Integer> map;
    int[] nums;
    int index;
    Random r;
    public RandomizedSet() {
        map=new HashMap<>();
        nums=new int[200001];
        index=-1;
        r=new Random();
    }
    
    public boolean insert(int val) {
        if(map.get(val)!=null)
            return false;
        nums[++index]=val;
        map.put(val,index);
        return true;
    }
    
    public boolean remove(int val) {
        if(map.get(val)==null)
            return false;
        int location=map.remove(val);
        //删除的不是最后一个元素
        if(location!=index)
            //将最后一个元素覆盖到待删除的元素位置上
            map.put(nums[index],location);
        //删除最后一个位置的元素
        nums[location]=nums[index--];
        return true;
    }
    
    public int getRandom() {
        return nums[r.nextInt(index+1)];
    }
}

总结

主要是利用哈希表存储元素的位置，然后利用数组插入删除，尽可能降低时间复杂度