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

Categories:

题目描述
思路分析
1. 解法一：数组 + 哈希表（推荐）
相似题目

题目描述

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

思路分析

解法一：数组 + 哈希表（推荐）

核心思路：

维护一个动态数组 nums 存储所有元素，哈希表 indexMap 存储每个值对应的数组下标。

insert：先检查元素是否存在，不存在则追加到数组末尾，并在哈希表中记录其下标，O(1)。

remove：将数组最后一个元素移到被删元素的位置，同步更新哈希表，再删除末尾元素，整个过程 O(1)。

getRandom：利用 Random 生成随机下标，直接按下标访问数组，O(1)。

删除时”末尾覆盖被删位置”是本题关键，避免了数组移位操作。

复杂度分析：

时间复杂度：O(1)，insert、remove、getRandom 均为 O(1)（均摊）

空间复杂度：O(n)，其中 n 为集合中元素的数量

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;

class RandomizedSet {

    // 存储所有元素的动态数组
    private final List<Integer> nums;
    // 哈希表：值 -> 在 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) {
        // 已存在则直接返回 false
        if (indexMap.containsKey(val)) {
            return false;
        }
        // 追加到数组末尾，记录下标
        indexMap.put(val, nums.size());
        nums.add(val);
        return true;
    }

    public boolean remove(int val) {
        // 不存在则直接返回 false
        if (!indexMap.containsKey(val)) {
            return false;
        }
        // 获取被删元素的下标
        int idx = indexMap.get(val);
        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
    // 哈希表：值 -> 在 nums 中的下标
    indexMap map[int]int
}

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

func (rs *RandomizedSet) Insert(val int) bool {
    // 已存在则直接返回 false
    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 {
    // 不存在则直接返回 false
    idx, ok := rs.indexMap[val]
    if !ok {
        return false
    }
    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))]
}

相似题目

题目	难度	考察点
381. O(1) 时间插入、删除和获取随机元素 - 允许重复	困难	哈希表、数组
432. 全 O(1) 的数据结构	困难	哈希表、双向链表
146. LRU 缓存	中等	哈希表、双向链表
460. LFU 缓存	困难	哈希表、双向链表
710. 黑名单中的随机数	困难	哈希表、随机化
528. 按权重随机选择	中等	前缀和、二分查找、随机化

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/92877767