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

实现RandomizedSet 类：

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

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

1. 动态数组 (nums)：存储元素值。数组支持通过索引 $O(1)$ 访问（nums[Math.floor(Math.random() * nums.length)]）。
2. 哈希表 (indices)：存储 val 到它在数组中 下标 的映射（val => index）。这让我们能在 $O(1)$ 时间内找到某个值在数组的哪个位置。

关键技巧：如何 $O(1)$ 删除？

普通数组删除中间元素是 $O(n)$，因为需要移动后面的元素。

技巧：将要删除的元素与数组的 最后一个元素交换，然后弹出末尾元素。这样只需要修改哈希表中最后一个元素的下标，时间复杂度就是 $O(1)$。

class RandomizedSet {
    private nums :number[]
    private set:Map<number,number>
    constructor() {
        this.nums = []
        this.set = new Map()
    }
 
    insert(val: number): boolean {
        if(this.set.has(val)) return false
 
        this.nums.push(val)
        this.set.set(val,this.nums.length-1)
        return true
    }
 
    remove(val: number): boolean {
        if(!this.set.has(val)) return false
 
        let index = this.set.get(val)
        let lastNum = this.nums[index]
        this.nums[index] = this.nums[this.nums.length-1]
        this.set.set(lastNum, index);
        this.nums.pop()
 
        this.set.delete(val)
        return true
        
    }
 
    getRandom(): number {
        const randomIndex = Math.floor(Math.random() * this.nums.length);
        return this.nums[randomIndex];
    }
}
 
/**
 * Your RandomizedSet object will be instantiated and called as such:
 * var obj = new RandomizedSet()
 * var param_1 = obj.insert(val)
 * var param_2 = obj.remove(val)
 * var param_3 = obj.getRandom()
 */