16-O(1) 时间插入、删除和获取随机元素

实现RandomizedSet 类：

RandomizedSet() 初始化 RandomizedSet 对象
bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。

你必须实现类的所有函数，并满足每个函数的平均时间复杂度为 O(1) 。

代码实现

class RandomizedSet {// 用于存储元素的数组private nums: number[];// 用于记录元素在数组中索引的哈希表private indexMap: Map<number, number>;constructor() {this.nums = [];this.indexMap = new Map();}insert(val: number): boolean {if (this.indexMap.has(val)) {return false;}// 将元素添加到数组末尾this.nums.push(val);// 记录元素在数组中的索引this.indexMap.set(val, this.nums.length - 1);return true;}remove(val: number): boolean {if (!this.indexMap.has(val)) {return false;}const index = this.indexMap.get(val)!;const lastIndex = this.nums.length - 1;const lastVal = this.nums[lastIndex];// 将数组最后一个元素移动到要删除元素的位置this.nums[index] = lastVal;// 更新最后一个元素在哈希表中的索引this.indexMap.set(lastVal, index);// 删除数组最后一个元素this.nums.pop();// 从哈希表中删除要删除的元素this.indexMap.delete(val);return true;}getRandom(): number {// 随机生成一个 0 到数组长度减 1 之间的索引const randomIndex = Math.floor(Math.random() * this.nums.length);return this.nums[randomIndex];}
}// 示例调用
const randomizedSet = new RandomizedSet();
console.log(randomizedSet.insert(1)); // 返回 true
console.log(randomizedSet.remove(2)); // 返回 false
console.log(randomizedSet.insert(2)); // 返回 true
console.log(randomizedSet.getRandom()); // 随机返回 1 或 2
console.log(randomizedSet.remove(1)); // 返回 true
console.log(randomizedSet.insert(2)); // 返回 false
console.log(randomizedSet.getRandom()); // 返回 2

代码解释

构造函数 constructor：
- 初始化一个空数组 nums 用于存储元素。
- 初始化一个空的 Map 对象 indexMap 用于记录每个元素在数组中的索引。
插入方法 insert：
- 检查 indexMap 中是否已经存在该元素，如果存在则返回 false。
- 若不存在，将元素添加到 nums 数组的末尾，并在 indexMap 中记录该元素的索引，最后返回 true。
删除方法 remove：
- 检查 indexMap 中是否存在该元素，如果不存在则返回 false。
- 若存在，获取该元素在数组中的索引 index 以及数组最后一个元素的索引 lastIndex 和值 lastVal。
- 将数组最后一个元素移动到要删除元素的位置，并更新 indexMap 中最后一个元素的索引。
- 删除数组最后一个元素，并从 indexMap 中删除要删除的元素，最后返回 true。
随机获取元素方法 getRandom：
- 使用 Math.random() 生成一个 0 到数组长度减 1 之间的随机整数作为索引。
- 返回该索引对应的数组元素。

复杂度分析

时间复杂度：insert、remove 和 getRandom 方法的平均时间复杂度均为 O(1)。insert 操作主要是数组的 push 和 Map 的 set 操作；remove 操作虽然涉及数组元素的移动，但只是常数级的操作；getRandom 操作是根据随机索引直接访问数组元素。
空间复杂度：O(n)，其中是集合中元素的数量，主要用于存储数组和哈希表。