380. O(1) 时间插入、删除和获取随机元素

实现RandomizedSet 类：

• RandomizedSet() 初始化 RandomizedSet 对象

• bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。

• bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。

• int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。

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

示例:

• 输入

["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]

• 输出

[null, true, false, true, 2, true, false, 2]

---

题解:哈希表+变长数组

该题要求O(1)时间复杂度实现元素的插入、删除和获取。变长数组虽然可以实现O(1)时间获取随机元素，但是无法在O(1)时间判断元素是否存在从而实现插入、删除；而哈希表可以在O(1)时间判断元素是否存在，实现插入和删除，但是由于不能下标定位现有元素，无法在O(1)时间公平地获取某一个元素。


故需要结合使用哈希表与变长数组。利用哈希表存储<元素,下标信息>,变长数组存储数据。

• 插入val时，先判断val是否已存在哈希表中，已存在返回false，不存在则将其插入变长数组尾部index处，将<val,index>插入哈希表，返回true。
• 删除val时，先判断val是否已存在哈希表中，不存在返回false，存在则将变长数组最后一个元素last覆盖待删除元素val，覆盖后将变长数组末尾多余的last删除，并在哈希表中删除val的记录,更新last的记录。
• 获取随机元素，使用随机数返回变长数组中随机下标的值。

代码

class RandomizedSet {
    List<Integer> nums;
    Map<Integer,Integer> indexInfo;
    Random random;

    public RandomizedSet() {
        nums=new ArrayList<Integer>();
        indexInfo = new HashMap<Integer,Integer>();
        random = new Random();
    }
    
    public boolean insert(int val) {
        if(indexInfo.containsKey(val)){
            return false;
        }
        int index=nums.size();
        nums.add(val);
        indexInfo.put(val,index);
        return true;
    }
    
    public boolean remove(int val) {
        if(!indexInfo.containsKey(val)){
            return false;
        }
        int index=indexInfo.get(val);
        int last=nums.get(nums.size()-1);
        nums.set(index,last);
        indexInfo.put(last,index);
        nums.remove(nums.size()-1);
        indexInfo.remove(val);
        return true;
    }
    
    public int getRandom() {
        int randomIndex=random.nextInt(nums.size());
        return nums.get(randomIndex);
    }
}

复杂度分析

• 时间复杂度：$$O(1)$$
• 空间复杂度：$$O(n)$$