【数组】常数时间查找/删除数组元素

[miracles1919]

参考：常数时间删除/查找数组中的任意元素

基本思路

• 用数组存储数据
• 用哈希表记录元素对应的索引
• 删除某个元素时，和元素尾部交换位置，然后 pop 并更新哈希表

[miracles1919]

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

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

/** 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.insert = function(val) {
    if (this.map.has(val)) return false
    const index = this.nums.length
    this.map.set(val, index)
    this.nums.push(val)

    return true
};

/** 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.remove = function(val) {
    if (!this.map.has(val)) return false
    const index = this.map.get(val)
    const lastNum = this.nums[this.nums.length -1]
    // 将val索引对应的元素更换为最后一个元素
    this.nums[index] = lastNum
    this.map.set(lastNum, index)

    this.nums.pop()
    this.map.delete(val)
    return true
};

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

[miracles1919]

710. 黑名单中的随机数

/**
 * @param {number} n
 * @param {number[]} blacklist
 */
// 将[0, n - 1]看做一个数组，将blacklist中的元素移动到数组末尾
// 即[k, n - 1]为blacklist，[0, k] 就是期望区间
var Solution = function (n, blacklist) {
    this.length = n - blacklist.length
    this.map = new Map()
    let last = n - 1
    for (let b of blacklist) {
        // 标记
        this.map.set(b, 1)
    }

    for (let b of blacklist) {
        // 在尾部的black直接跳过
        if (b >= this.length) continue
        while (this.map.has(last)) {
            last--
        }
        // 将black映射到尾部
        this.map.set(b, last--)
    }
};

/**
 * @return {number}
 */
Solution.prototype.pick = function () {
    const randomIndex = Math.floor(Math.random() * this.length)
    if (this.map.has(randomIndex)) return this.map.get(randomIndex)
    return randomIndex
};