LeetCode 381. O(1) 时间插入、删除和获取随机元素 - 允许重复

2026-03-16 HGNULB 约 7 分钟

文章信息 9 个分类 5 个标签

分类

题目描述

✅ 381. O(1) 时间插入、删除和获取随机元素 - 允许重复

题意分析

要设计一个可以装重复元素的多重集合，支持三个操作：放入一个值、删掉这个值的任意一份、以及等概率随机取出一份。三者的平均代价都必须是常数。

两个返回值的语义要看清楚。放入时返回「放入之前集合里是否还没有这个值」，也就是说重复放入第二份时返回假，但那一份依然要真实入库；删除时返回「集合里当时是否存在这个值」，不存在就返回假且不做任何改动，存在则只删掉其中一份而不是全部。

随机取出的分布也有讲究：题目要求每一份出现被抽中的概率相同，而不是每个不同的值被抽中的概率相同。所以若集合里有两个 $1$ 和一个 $2$，抽到 $1$ 的概率应是三分之二。这直接决定了底层必须按「出现次数」而不是「去重后的值」来组织。

常数时间这一硬性要求排除了排序、链表遍历和任何按值扫描的方案，只剩下哈希与数组的组合。调用次数上界在 $2 \times 10^5$ 量级，值域是整型全域，所以按值开数组不现实，必须用哈希表。

边界情形包括：删除一个从未出现过的值；把某个值的所有副本删光后再次放入，此时返回值应重新变为真；以及待删的那一份恰好就位于内部数组的末尾——这一种是实现里最容易写错的分支。题目保证 getRandom 只在集合非空时调用。

解法：动态数组 + 下标集合

核心思路

getRandom 要做到 $O(1)$，最自然的存储是动态数组：在有效下标范围内均匀随机，就能保证每个元素副本等概率被选中。难点转移到删除——数组中间删除会搬移后缀，无法达到常数时间。

这里不要求保持顺序，因此可用数组末尾元素覆盖待删位置，再删除末尾。为了 $O(1)$ 找到待删位置，用哈希表 indices 记录“值 → 该值当前占用的全部下标”。允许重复，所以映射值必须是集合，不能只是一个下标。

核心不变量是：数组中的每个有效下标，都恰好出现在对应值的下标集合中；集合里的每个下标，也必须指回数组中的同一个值。insert 增加一对记录，remove 在交换末尾元素时同步改两边的下标，三个操作结束后都恢复该不变量。

随机性的正确性来自“一份元素对应一个数组位置”。若数组当前有 $m$ 个副本，均匀抽取一个下标后，每一份被选中的概率都是 $1/m$；重复值占据多个位置，其总概率自然与出现次数成正比。

解题步骤

insert(val)：先判断该值是否尚未出现，再把当前数组长度加入 indices[val]，最后把 val 追加到数组。

remove(val)：若没有对应下标，返回 false；否则从集合中任取一个 removeIndex。

记录 lastIndex 和 lastValue。若待删位置不是末尾，就用 lastValue 填坑，并把它的下标记录由 lastIndex 改为 removeIndex。

删除数组末尾；若 val 的下标集合已空，同时删除这个键，返回 true。

getRandom()：在 [0, values.size()) 中均匀生成下标并返回数组元素。

例如数组为 [1, 1, 2]，删除下标 0 上的 1：先把末尾的 2 搬到下标 0，再把 indices[2] 从 {2} 改成 {0}，最后砍掉末尾，得到 [2, 1]。数组与索引表仍完全对应。

代码实现

import java.util.*;
import java.util.concurrent.ThreadLocalRandom;

class RandomizedCollection {
    private final List<Integer> values = new ArrayList<>();
    private final Map<Integer, Set<Integer>> indices = new HashMap<>();

    public boolean insert(int val) {
        Set<Integer> set = indices.computeIfAbsent(val, key -> new HashSet<>());
        boolean first = set.isEmpty();
        set.add(values.size());
        values.add(val);
        return first;
    }

    public boolean remove(int val) {
        Set<Integer> removeSet = indices.get(val);
        if (removeSet == null) {
            return false;
        }

        int removeIndex = removeSet.iterator().next();
        int lastIndex = values.size() - 1;
        int lastValue = values.get(lastIndex);
        removeSet.remove(removeIndex);

        if (removeIndex != lastIndex) {
            values.set(removeIndex, lastValue);
            Set<Integer> lastSet = indices.get(lastValue);
            lastSet.remove(lastIndex);
            lastSet.add(removeIndex);
        }

        values.remove(lastIndex);
        if (removeSet.isEmpty()) {
            indices.remove(val);
        }
        return true;
    }

    public int getRandom() {
        int index = ThreadLocalRandom.current().nextInt(values.size());
        return values.get(index);
    }
}

import "math/rand"

type RandomizedCollection struct {
    values  []int
    indices map[int]map[int]struct{}
}

func Constructor() RandomizedCollection {
    return RandomizedCollection{indices: make(map[int]map[int]struct{})}
}

func (this *RandomizedCollection) Insert(val int) bool {
    set, exists := this.indices[val]
    if !exists {
        set = make(map[int]struct{})
        this.indices[val] = set
    }

    set[len(this.values)] = struct{}{}
    this.values = append(this.values, val)
    return !exists
}

func (this *RandomizedCollection) Remove(val int) bool {
    removeSet, exists := this.indices[val]
    if !exists {
        return false
    }

    removeIndex := 0
    for index := range removeSet {
        removeIndex = index
        break
    }

    lastIndex := len(this.values) - 1
    lastValue := this.values[lastIndex]
    delete(removeSet, removeIndex)

    if removeIndex != lastIndex {
        this.values[removeIndex] = lastValue
        lastSet := this.indices[lastValue]
        delete(lastSet, lastIndex)
        lastSet[removeIndex] = struct{}{}
    }

    this.values = this.values[:lastIndex]
    if len(removeSet) == 0 {
        delete(this.indices, val)
    }
    return true
}

func (this *RandomizedCollection) GetRandom() int {
    return this.values[rand.Intn(len(this.values))]
}

复杂度分析

时间复杂度：insert、remove、getRandom 的期望时间均为 $O(1)$。动态数组追加和哈希表操作按均摊、期望复杂度计算。

空间复杂度：$O(n)$，其中 $n$ 是当前保存的元素总数。数组存 $n$ 个副本，所有下标集合合计也存 $n$ 个下标。

关键点总结

随机等概率访问需要紧凑数组；常数时间删除需要“末尾填坑”。

重复元素对应多个位置，因此维护“值到下标集合”，而不是“值到单一下标”。

真正要守住的是数组与索引表的双向一致性，交换后必须同时更新末尾值的旧、新下标。

哈希操作是期望 $O(1)$，动态数组尾部追加是均摊 $O(1)$，面试时应准确说明口径。

易错点总结

insert 在加入新下标后才判断是否首次出现，会把第一次插入错误地返回 false。

删除中间位置时只改数组、不改 indices[lastValue]，会留下失效下标。

removeIndex == lastIndex 时仍执行交换，可能把刚删除的下标重新加入集合。

被搬运的 lastValue 可能恰好等于 val；按“先移除待删下标，再替换末尾下标”的顺序处理即可。

getRandom 若在不同值之间随机，会让每个值等概率，而不是让每个元素副本等概率。

Java 的数组下标要保持 int；若传入装箱后的 Integer 调用 List.remove，可能误走“按值删除”的重载。

相似题目

题目	难度	考察点
380. O(1) 时间插入、删除和获取随机元素	中等	不含重复，映射的值退化为单个下标，没有「同值搬运」这个分支
LCR 030. O(1) 时间插入、删除和获取随机元素	中等	与 380 同题异名，可用来检验去重版本的写法是否已经完全熟练
710. 黑名单中的随机数	困难	同为等概率采样，但要靠一次性建立的映射把黑名单位置折叠到合法区间
528. 按权重随机选择	中等	概率不再均匀，靠前缀和加二分实现加权采样，代价是 $O(\log n)$
398. 随机数索引	中等	在重复值中等概率选下标，可用蓄水池抽样做到常数空间而无需预处理
146. LRU 缓存	中等	同为哈希表配合另一种结构达成常数操作，但辅助结构是双向链表且需维护顺序