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

Categories:

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

题目描述

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

思路分析

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

核心思路：

用动态数组保存元素，保证 getRandom 为 O(1)。

哈希表记录每个值对应的下标集合，支持重复元素。

删除时用末尾元素覆盖被删位置，并更新下标集合。

复杂度分析：

时间复杂度：O(1)，所有操作均为均摊常数时间。

空间复杂度：O(n)，存储数组和下标集合。

class RandomizedCollection {
    private final List<Integer> nums;
    private final Map<Integer, Set<Integer>> indexMap;
    private final Random random;

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

    public boolean insert(int val) {
        boolean notExist = !indexMap.containsKey(val) || indexMap.get(val).isEmpty();

        indexMap.computeIfAbsent(val, k -> new HashSet<>()).add(nums.size());
        nums.add(val);

        return notExist;
    }

    public boolean remove(int val) {
        Set<Integer> set = indexMap.get(val);
        if (set == null || set.isEmpty()) {
            return false;
        }

        int removeIdx = set.iterator().next();
        int lastIdx = nums.size() - 1;
        int lastVal = nums.get(lastIdx);

        // 将末尾元素覆盖到被删除位置
        nums.set(removeIdx, lastVal);

        set.remove(removeIdx);
        Set<Integer> lastSet = indexMap.get(lastVal);
        lastSet.remove(lastIdx);
        if (removeIdx != lastIdx) {
            lastSet.add(removeIdx);
        }

        nums.remove(lastIdx);
        return true;
    }

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

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

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

func (rc *RandomizedCollection) Insert(val int) bool {
    _, exists := rc.indexMap[val]
    if !exists {
        rc.indexMap[val] = make(map[int]struct{})
    }

    rc.indexMap[val][len(rc.nums)] = struct{}{}
    rc.nums = append(rc.nums, val)

    return !exists
}

func (rc *RandomizedCollection) Remove(val int) bool {
    set, ok := rc.indexMap[val]
    if !ok || len(set) == 0 {
        return false
    }

    var removeIdx int
    for idx := range set {
        removeIdx = idx
        break
    }

    lastIdx := len(rc.nums) - 1
    lastVal := rc.nums[lastIdx]

    // 将末尾元素覆盖到被删除位置
    rc.nums[removeIdx] = lastVal

    delete(set, removeIdx)
    lastSet := rc.indexMap[lastVal]
    delete(lastSet, lastIdx)
    if removeIdx != lastIdx {
        lastSet[removeIdx] = struct{}{}
    }

    rc.nums = rc.nums[:lastIdx]
    return true
}

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

相似题目

题目	难度	考察点
380. O(1) 时间插入、删除和获取随机元素	中等	哈希表、数组
382. 链表随机节点	中等	随机化
398. 随机数索引	中等	哈希表、随机化
384. 打乱数组	中等	随机化
710. 黑名单中的随机数	困难	哈希表、随机化

本文作者: HGNULB

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