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

约 6 分钟
文章信息 5 个分类 6 个标签
分类
LeetCode 中等 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
数组 哈希表 数学 LCR 设计 随机化

题目描述

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

image-20260928235218802

image-20260928235218805

题意分析

设计一个不含重复值的集合，支持插入、删除和等概率随机取值，三个操作都要求平均 $O(1)$ 时间。插入已有值、删除不存在的值都返回 false，成功改变集合时返回 true。

数组方便按随机下标访问，哈希表方便按值定位。把两者组合起来，再利用“集合不要求保持元素顺序”的条件，就能同时满足这些操作。题目保证调用 getRandom 时集合非空。

解法：数组与下标映射

核心思路

[!blue]

用动态数组 nums 保存全部元素，用 indexMap 保存“元素值 → 数组下标”。始终保持每个元素只出现一次，且 nums[indexMap[v]] == v，这样既能按下标取值，也能按值找到位置。

插入时先查哈希表，确认不存在后，把当前数组长度记为新元素下标，再将元素追加到末尾。数组可能偶尔扩容，但追加的均摊成本仍为常数。

删除时先找到下标 idx。不必把后续元素整体前移，而是用末尾元素 last 覆盖 idx，将 last 的下标改为 idx，再删除数组末尾和目标值的哈希记录。集合顺序可以变化，因此一次覆盖就能保持数组紧凑，其他元素无需移动。

要先更新末尾元素的映射，最后删除目标键。若删的恰好就是末尾元素，last 与目标值相同，最后这次删除才能确保它不再留在哈希表中；唯一元素也能由同一过程处理。

随机取值时，在 [0, nums.size()) 中均匀选择一个下标。数组没有空位，每个现存值恰好占一个位置，所以每个值被返回的概率都是 1 / size。

解题步骤

  1. 构造时初始化空数组、空下标表；Java 同时创建供后续调用复用的随机数对象。
  2. insert 先查重，已存在则返回 false；否则记录追加前的数组长度，追加元素，返回 true。
  3. remove 先查下标，不存在则返回 false；否则取末尾值覆盖目标位置，并同步更新末尾值的映射。
  4. 删除数组末尾，再删除目标值的哈希记录，返回 true。
  5. getRandom 生成合法范围内的随机下标，直接返回数组中对应的值。

代码实现

class RandomizedSet {

    private final List<Integer> nums;
    private final Map<Integer, Integer> indexMap;
    private final Random random;

    public RandomizedSet() {
        nums = new ArrayList<>();
        indexMap = new HashMap<>();
        random = new Random();
    }

    public boolean insert(int val) {
        if (indexMap.containsKey(val)) {
            return false;
        }

        // 取的是追加之前的长度，正好是新元素落位后的下标。
        indexMap.put(val, nums.size());
        nums.add(val);

        return true;
    }

    public boolean remove(int val) {
        if (!indexMap.containsKey(val)) {
            return false;
        }

        int idx = indexMap.get(val);
        // 用末尾元素覆盖待删位置，把 O(n) 的搬移变成 O(1) 的覆盖。
        int last = nums.get(nums.size() - 1);

        nums.set(idx, last);
        indexMap.put(last, idx);
        nums.remove(nums.size() - 1);
        // 最后删除目标键，避免末尾元素就是目标值时仍留下映射。
        indexMap.remove(val);

        return true;
    }

    public int getRandom() {
        return nums.get(random.nextInt(nums.size()));
    }
}

import (
    "math/rand"
)

type RandomizedSet struct {
    nums     []int
    indexMap map[int]int
}

func Constructor() RandomizedSet {
    return RandomizedSet{
        nums:     []int{},
        indexMap: make(map[int]int),
    }
}

func (rs *RandomizedSet) Insert(val int) bool {
    if _, ok := rs.indexMap[val]; ok {
        return false
    }
    // 取的是追加之前的长度，正好是新元素落位后的下标。
    rs.indexMap[val] = len(rs.nums)
    rs.nums = append(rs.nums, val)
    return true
}

func (rs *RandomizedSet) Remove(val int) bool {
    idx, ok := rs.indexMap[val]
    if !ok {
        return false
    }
    // 用末尾元素覆盖待删位置，把 O(n) 的搬移变成 O(1) 的覆盖。
    last := rs.nums[len(rs.nums)-1]
    rs.nums[idx] = last
    rs.indexMap[last] = idx
    rs.nums = rs.nums[:len(rs.nums)-1]
    // 最后删除目标键，避免末尾元素就是目标值时仍留下映射。
    delete(rs.indexMap, val)
    return true
}

func (rs *RandomizedSet) GetRandom() int {
    return rs.nums[rand.Intn(len(rs.nums))]
}

复杂度分析

  • 时间复杂度：三个操作均为平均 $O(1)$。哈希操作按平均成本计算，动态数组追加按扩容后的均摊成本计算，覆盖与尾删只修改固定数量的位置。
  • 空间复杂度：$O(n)$，其中 n 为操作过程中集合的最大规模；数组和下标表各保存一份元素信息，底层容量可能在删除后保留。

关键点总结

[!green]

  • 数组提供随机访问，下标表提供按值定位，两者通过同一条下标关系保持同步。
  • 删除可以改变元素顺序，因此可用末尾覆盖代替整体搬移。
  • 每个值只对应一个紧凑数组位置，均匀选择下标就等价于均匀选择元素。

易错点总结

[!yellow]

  • 插入必须先查重，否则同一值占据多个位置，会同时破坏集合语义和随机概率。
  • 移动末尾元素后必须更新它的下标，不能只改数组而留下旧映射。
  • 更新搬移映射要先于删除目标键，尤其需要覆盖删除末尾或唯一元素的情况。
  • 随机下标的上界不能包含数组长度；题目已保证集合非空，无需增加空集合返回值。

相似题目

题目 难度 关联与区别
381. O(1) 时间插入、删除和获取随机元素 - 允许重复 困难 同样用数组末尾覆盖被删位置，原题允许重复值，需要值到多个下标的映射。
710. 黑名单中的随机数 困难 同样把随机选择转成均匀整数下标抽样，原题用重映射避开黑名单，本题维护动态紧凑数组。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/27146301
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！