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]

解释
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomizedSet.remove(2); // 返回 false ，表示集合中不存在 2 。
randomizedSet.insert(2); // 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
randomizedSet.getRandom(); // getRandom 应随机返回 1 或 2 。
randomizedSet.remove(1); // 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
randomizedSet.insert(2); // 2 已在集合中，所以返回 false 。
randomizedSet.getRandom(); // 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。

提示：

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

题解：

‍

这道题的本质是用「数组 + 哈希表」互补，同时满足三个操作的平均 O (1) 复杂度，单独用任意一种数据结构都做不到：

只用数组：插入末尾、随机读取是 O (1)，但删除中间元素需要移动后续所有元素，最坏 O (n)。
只用哈希表：插入、删除、查找是 O (1)，但无法通过下标随机访问，做不到等概率随机返回元素。

所以我们做分工：

数组（nums）：存储所有实际元素，支持 O (1) 随机下标访问，保证 getRandom 等概率。
哈希表（map）：存储 值 -> 数组下标 的映射，支持 O (1) 查找元素所在位置，保证 insert/remove 快速定位。

逐个操作逐行详解

我们以 Java 版代码为例，对应每一步逻辑讲清楚。

insert (int val) —— 插入元素

目标：元素不存在则插入，返回 true；已存在则返回 false。

public boolean insert(int val) {
    if (map.containsKey(val)) return false; // 1. 哈希表查一下，已经有就直接返回失败
    nums[++idx] = val;                      // 2. 把新元素放到数组的末尾
    map.put(val, idx);                      // 3. 哈希表记录：这个值对应的数组下标
    return true;
}

数组只在末尾追加元素，时间 O (1)；
哈希表新增一条键值对，时间 O (1)；
全程保证集合里元素不重复。
remove (int val) —— 删除元素（最核心的技巧）

难点：数组删除中间位置元素，原本需要把后面所有元素往前挪，时间 O (n)。解法：将要删除的元素，和数组最后一个元素交换位置，然后直接删掉数组末尾。这样只修改 1 个位置，其他元素完全不动，时间 O (1)。

public boolean remove(int val) {
    if (!map.containsKey(val)) return false;   // 1. 哈希表查一下，没有就直接返回失败
    int loc = map.remove(val);                 // 2. 取出要删元素的数组下标 loc，同时从哈希表删掉 val
    if (loc != idx) map.put(nums[idx], loc);   // 3. 如果删的不是最后一个元素：把末尾元素的下标更新为 loc
    nums[loc] = nums[idx--];                   // 4. 用末尾元素覆盖掉 loc 位置的值，然后数组长度-1
    return true;
}

我们把第 3、4 步拆开讲透：

nums[idx] 是数组最后一个有效元素；
我们把它的值放到 loc 位置，相当于 “把最后一个元素移到了被删除的空位上”；
同时必须更新哈希表：这个末尾元素的下标从 idx 变成了 loc；
最后 idx-- 相当于把数组末尾删掉，因为我们已经把末尾元素移到前面了。

边界补充：如果要删的元素刚好就是数组最后一个（loc == idx），那就不用交换和更新哈希表，直接 idx-- 删掉末尾即可。

简单来说就是：如有数组是[10, 20, 30, 40, 50]，对应map就为map = {10:0, 20:1, 30:2, 40:3, 50:4}；此时idx = 4(数组最后一个元素的下不标)如果想要删除集合中的20，remove(20)，也就是 val = 20。

if (!map.containsKey(val)) return false;

map 里有 20，继续。

取出 loc，同时从 map 删掉 val

int loc = map.remove(val);

map.remove(20) 做了两件事：① 返回 20 对应的下标 1；② 把 20:1 这条记录从 map 里删掉。
所以 loc = 1。（要删除的val在数组里的下标位置）

现在状态：

nums = [10, 20, 30, 40, 50]   (数组还没改)
map  = {10:0, 30:2, 40:3, 50:4}  (20 已经被删了)
idx  = 4
loc  = 1

第 3 步：如果删的不是末尾元素，更新末尾元素的下标

if (loc != idx) map.put(nums[idx], loc); // loc（要删除的val在数组里的下标位置） 不等于 idx（数组当前最后一个有效元素的下标） 所以删除的元素部署末尾元素
// num[idx]为50，即当前数组的最后一个元素，map.put(nums[idx], loc)将其下标改为要删除元素的下标

loc = 1，idx = 4，不相等，所以要执行。
nums[idx] = nums[4] = 50（数组最后一个元素的值）
map.put(50, 1)：把 50 的下标从 4 改成 1。
现在状态：

nums = [10, 20, 30, 40, 50] （数组还没有删除） map = {10:0, 30:2, 40:3, 50:1} (50 的下标改成了 1) （map的val为20的值已经删除，且下标更新） idx = 4 loc = 1

第 4 步：用末尾元素覆盖 loc 位置，然后 idx--

nums[loc] = nums[idx--];// 开始更改数组，数组的要删除的元素的位置的值num[loc]变为数组末尾的元素nums[idx]

这一行拆开看：

nums[idx] = nums[4] = 50
nums[loc] = nums[1] = 50（把 50 写到位置 1，覆盖掉原来的 20）
idx--：idx 从 4 变成 3

最终状态：

nums = [10, 50, 30, 40, 50] // 要删除的20的位置已经被赋值为50，同时由于idx = 3,所以最后一个残留的50是不算有效元素的
         0   1   2   3   4
                     ↑
                    idx=3 (有效范围只到下标3)
map  = {10:0, 30:2, 40:3, 50:1}

注意：下标 4 那个位置还残留着 50，但 idx = 3 了，所以它已经不算有效元素了，以后插入时**nums[++idx] = val;**会直接覆盖它。

getRandom () —— 随机返回元素

public int getRandom() {
    return nums[random.nextInt(idx + 1)];
}

数组下标范围是 0 ~ idx，共 idx+1 个元素；
随机生成一个范围内的整数下标，直接返回数组对应值；
每个下标被抽到的概率完全相等，满足题目 “相同概率” 要求。

class RandomizedSet {
    static int[] nums = new int[200010];
    Random random = new Random();
    Map<Integer, Integer> map = new HashMap<>();
    int idx = -1;
    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 loc = map.remove(val);
        if (loc != idx) map.put(nums[idx], loc);
        nums[loc] = nums[idx--];
        return true;
    }
    public int getRandom() {
        return nums[random.nextInt(idx + 1)];
    }
}

作者：宫水三叶
链接：https://leetcode.cn/problems/insert-delete-getrandom-o1/solutions/1416888/by-ac_oier-tpex/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

‍