题目要求

思路：哈希表+数组

$O (1)$ 复杂度的插入和删除很明显是用哈希表，但是取随机数的话用数组返回随机下标比较方便，所以就同时维护一个哈希表和一个数组，哈希表存着数组内元素及其对应下标。

直接根据数据范围（ $2*10^5$ ）申请一个固定大小的数组，为了方便取随机数，要维护数组的「前 $i d x$ 个元素都不空」，所以在删除元素时要把当前最后一个元素 $n u m s [i d x]$ 放到被删除的元素处 $n u m s [d e l]$ 补空。
此时随机操作直接在 $[0, i d x]$ 内取随机值作为下标，返回数组内对应值即可。

而对于插入操作，则判断是否存在于哈希表中，然后同时维护哈希表和数组即可。

Java

class RandomizedSet {
    static int[] nums = new int[200001];
    Random random = new Random();
    Map<Integer, Integer> map = new HashMap<>(); //数组下标与值
    int idx = -1;
    public RandomizedSet() {}
    
    public boolean insert(int val) {
        if(map.containsKey(val))
            return false;
        nums[++idx] = val;
        map.put(val, idx);
        return true;
    }
    
    public boolean remove(int val) {
        if(!map.containsKey(val))
            return false;
        int del = map.remove(val);
        if(del != idx) //是否删除最后一个元素
            map.put(nums[idx], del);
        nums[del] = nums[idx--]; //补空，保证前面都是满的
        return true;
    }
    
    public int getRandom() {
        return nums[random.nextInt(idx + 1)];
    }
}

时间复杂度：所有操作均 $O (1)$
空间复杂度： $O (n)$ ，数组和哈希表均为 $O (n)$

C++

class RandomizedSet {
private:
    int nums[200001];
    unordered_map<int, int> map;
    int idx = -1;
public:
    RandomizedSet() {}
    
    bool insert(int val) {
        if(map.count(val))
            return false;
        nums[++idx] = val;
        map[val] = idx;
        return true;
    }
    
    bool remove(int val) {
        if(!map.count(val))
            return false;
        int del = map[val];
        map.erase(val);
        if(del != idx) //是否删除最后一个元素
            map[nums[idx]] = del;
        nums[del] = nums[idx--]; //补空，保证前面都是满的
        return true;
    }
    
    int getRandom() {
        return nums[rand() % (idx+1)];
    }
};

时间复杂度：所有操作均 $O (1)$
空间复杂度： $O (n)$ ，数组和哈希表均为 $O (n)$

STL unordered_map

学习参考链接
即为一个无序的map容器，以键值对形式存在，键不能相等。

方法	功能	备注
$e m p l a c e ()$	插入元素，效率高于insert()
$c o u n t (k e y)$	查找键值为 $k e y$ 的键值对个数	上文使用判断是否存在键值为 $k e y$ 的元素
$f i n d (k e y)$	查找键值为 $k e y$ 的键值对，返回相应正向迭代器，若未找到则返回最后一个键值对之后位置的迭代器【即 $e n d ()$ 方法的返回值】	上文判断处也可换为此方法，即`map.find(key) == map.end()`则不存在，反之则存在
$e r a s e (k e y)$	删除以 $k e y$ 为键的键值对