案例

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

实现RandomizedSet 类：

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

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

示例：

输入
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
输出
[null, true, false, true, 2, true, false, 2]

解释
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomizedSet.remove(2); // 返回 false ，表示集合中不存在 2 。
randomizedSet.insert(2); // 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
randomizedSet.getRandom(); // getRandom 应随机返回 1 或 2 。
randomizedSet.remove(1); // 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
randomizedSet.insert(2); // 2 已在集合中，所以返回 false 。
randomizedSet.getRandom(); // 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。

self

设计思路

用一个hash表来存储和维护数据。

优化空间：

1. 利用数组的查询优势
2. 利用 hash 结构的插入和删除优势

var RandomizedSet = function () {
    this.obj = {}
};

/** 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.insert = function (val) {
    if (this.obj[val] || this.obj[val] === 0) return false
    this.obj[val] = val
    return true
};

/** 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.remove = function (val) {
    if (this.obj[val] || this.obj[val] === 0) {
        delete this.obj[val]
        return true
    }
    return false
};

/**
 * @return {number}
 */
RandomizedSet.prototype.getRandom = function () {
    const keys = Object.keys(this.obj);
    const randomKey = keys[Math.floor(Math.random() * keys.length)];
    return randomKey;
};

优化后的代码

var RandomizedSet = function () {
    this.arr = []
    this.map = new Map()
};

/** 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.insert = function (val) {
    if (this.map.has(val)) return false;
    let index = this.arr.length;
    this.arr.push(val)
    // 存储 index ,方便后面删除
    this.map.set(val, index)
    return true
};

/** 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.remove = function (val) {
    if (this.map.has(val)) {
        // 移除元素
        let index = this.map.get(val)
        this.arr[index] = this.arr[this.arr.length - 1];
        this.map.set(this.arr[index], index);
        this.arr.pop();

        // 移除 hash 中的元素
        this.map.delete(val)
        return true
    }
    return false
};

/**
 * @return {number}
 */
RandomizedSet.prototype.getRandom = function () {
    // 获取随机序列号
    const index = Math.floor(Math.random() * this.arr.length);
    return this.arr[index];
};