企业官网建设流程全解析

LeetCode 380「O(1) 时间插入、删除和获取随机元素」的核心是数组 + 哈希表组合：数组保证随机访问 O(1)，哈希表记录每个值在数组中的下标，保证查找和删除 O(1)。

题目回顾

实现 RandomizedSet 类，要求三个操作平均时间复杂度都是 O(1)：

• insert(val)：插入值，已存在返回 false
• remove(val)：删除值，不存在返回 false
• getRandom()：等概率返回集合中任意一个元素

核心设计
操作 数组 哈希表
insert 尾部追加 O(1) 记录 val → index O(1)
remove 与末尾元素交换后 pop O(1) 更新被交换元素的下标，再删除 O(1)
getRandom list.get(rand) O(1) 不需要

删除的 trick：数组删除任意位置元素本身是 O(n)，但把目标元素和末尾元素交换、再删除末尾，就变成了 O(1)。交换后记得同步更新哈希表中末尾元素的新下标。

Java 实现

class RandomizedSet {

private final java.util.ArrayList<Integer> list; private final java.util.HashMap<Integer, Integer> valToIndex; // val -> index in list private final java.util.Random random; public RandomizedSet() { list = new java.util.ArrayList<>(); valToIndex = new java.util.HashMap<>(); random = new java.util.Random(); } public boolean insert(int val) { if (valToIndex.containsKey(val)) { return false; } valToIndex.put(val, list.size()); list.add(val); return true; } public boolean remove(int val) { if (!valToIndex.containsKey(val)) { return false; } int idx = valToIndex.get(val); int last = list.get(list.size() - 1); // 把末尾元素搬到 idx 位置 list.set(idx, last); valToIndex.put(last, idx); // 删除尾部（O(1)）和哈希表中的 val list.remove(list.size() - 1); valToIndex.remove(val); return true; } public int getRandom() { return list.get(random.nextInt(list.size())); }

}

手动推演

insert(1) → true list=[1], map={1:0}
insert(2) → true list=[1,2], map={1:0, 2:1}
insert(2) → false （已存在）
getRandom() → 1 或 2，各 50%
remove(1) → true 交换 1↔2 → list=[2,2] → pop → list=[2], map={2:0}
remove(1) → false （已不存在）

复杂度

• 时间：三个操作均为 O(1) 平均
• 空间：O(n)，数组和哈希表各存 n 个元素

面试加分点

1. 为什么不用 HashSet？ —— HashSet 无法 O(1) 随机访问元素，getRandom() 做不到。
2. 为什么不用纯数组？ —— 删除时查找元素位置需要 O(n)。
3. 删除时交换的必要性：强调「交换 + 删尾」是把数组任意删除从 O(n) 降到 O(1) 的关键。
4. 线程安全：可以提一句 Collections.synchronizedList / ConcurrentHashMap，但本题通常不要求。
5. 变体：若允许重复元素（LeetCode 381），哈希表的 value 改成 HashSet 存多个下标即可。

需要我把 381（允许重复的版本）也一起写了，对比着看会更清楚 Map<Integer, Set> 的处理方式。