常数时间删除/查找数组中的任意元素 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：常数时间删除/查找数组中的任意元素

评论礼仪 见这里，违者直接拉黑。

[jzhou3700]

用map来进行映射的时候，查找数字的时候，不也存在hash冲突的问题嘛，这个不是和hashset一样的嘛

[ibuistheone]

This is a comment

[labuladong]

@jzhou3700 是存在哈希冲突，不过哈希冲突不影响时间复杂度。这道题关键在于要等概率，底层必须用紧凑存储的数组，才能做到等概率获取元素。

[alannesta]

类似LRU的hash配合double linked list也是可行的吧. val作为hash table的key, 返回随机元素就是从hash.keys( ) 里随机返回即可, 不需要遍历double linked list.

[labuladong]

@alannesta 不对，和 LRU 半毛钱关系都没有，你说「从 hash.keys( ) 里随机返回」，这个功能怎么实现？不就回到本文讲的这道算法题么？标准的 hash table 根本无法提供「随机返回一个 key」这样的功能，因为 key 的索引是分散在底层 table 上面的，没办法做到 O(1) 时间内随机取一个出来。

像 Python dict 这样提供随机 pop key 的功能，是因为它的 dict 对 hash table 底层实现做了类似本题的改造。

[venusDo]

东哥，黑名单的那题。如果从一开始解题，先把思路写出来；然后一步步带着怎么得到思路感觉会好很多。
我的理解是，把数组分为前后两部分，前部分的黑名单数据索引到后半部非黑名单数据。
但是这个理解的得出就要吃力
谢谢

[fornobugworld]

黑名单看着确实有点难理解，可不可以修改数组，直接把黑名单都移动到后面，这样省着映射了。。

[Chris-zhang1]

是啊我也有这个疑惑

[labuladong]

看题，输入只是一个 n，且 n 的数据规模非常大，难道你要创建一个大小为 n 的数组出来吗？

[deepbreath373]

Java Version

/**
 * LC380
 */
class RandomizedSet {
    List<Integer> list;
    HashMap<Integer, Integer> valToIndex;
    Random random;
    public RandomizedSet() {
        list = new ArrayList<>();
        valToIndex = new HashMap<>();
        random = new Random();
    }
    
    public boolean insert(int val) {
        if(valToIndex.containsKey(val)){
            return false;
        }
        list.add(val);
        valToIndex.put(val, list.size()-1);
        return true;
    }
    
    public boolean remove(int val) {
        if(!valToIndex.containsKey(val)){
            return false;
        }
        int index = valToIndex.get(val);
        int last = list.get(list.size() - 1);
        list.set(index, last);
        list.remove(list.size() - 1);
        valToIndex.put(last, index);
        valToIndex.remove(val);
        return true;
    }
    
    public int getRandom() {
        return list.get(random.nextInt(list.size()));
    }
}

/**
 * LC710
 */
class Solution {
    int size = 0;
    HashMap<Integer, Integer> map = new HashMap<>();
    public Solution(int n, int[] blacklist) {
        size = n - blacklist.length;
        for(int item : blacklist){
            map.put(item, -1);
        }
        int last = n - 1;
        for(int item : blacklist){
            if(item >= size){
                continue;
            }
            while(map.containsKey(last)){
                last--;
            }
            map.put(item, last);
            last--;
        }
    }
    
    public int pick() {
        int index = (int)(Math.random()*size);
         return map.getOrDefault(index, index);
        // if(map.containsKey(index)){
        //     return map.get(index);
        // }
        // return index;
    }
}

[Filggy]

    valToIndex.put(val, list.size()-1);

插入操作，这儿为什么是list.size()还要减一呢？

[PengHongfu]

class Solution {
    int length;
    HashMap<Integer,Integer> map;
    Random random;
    public Solution(int n, int[] blacklist) {
        random = new Random();
        //因为黑名单都在n中，所以，随机数在[0,length)中取
        length =  n - blacklist.length;
        map = new HashMap<>();

        //标记黑名单
        for(int b :blacklist){
            map.put(b, -1);
        }
        int index = length;
        //把黑名单中的数和length之后不是黑名单的数替换，用map记录
        for(int black : blacklist){
            //如果black不在[0,length)区间内 不用替换
            if(0 <= black && black < length){
                while(index < n){
                    if(!map.containsKey(index)){
                        //map记录
                        map.put(black, index);
                        index++;
                        break;
                    }else{
                      index++;
                    }
                }
            }
        }
    }
    
    public int pick() {
        int i = random.nextInt(length);
        if(map.containsKey(i)){
            return map.get(i);
        }   
        return i;
    }
}

[jswxwxf]

js 版黑名单中的随机数

class Solution {
  constructor(N, blacklist) {
    this.N = N;
    this.blacklist = blacklist;
    const mapping = Object.create(null);
    // 最终数组中的元素个数
    const sz = (this.sz = N - blacklist.length);
    // 先将所有黑名单数字加入 map
    for (const b of blacklist) {
      // 这里赋值多少都可以
      // 目的仅仅是把键存进哈希表
      // 方便快速判断数字是否在黑名单内
      mapping[b] = -1;
    }
    // 最后一个元素的索引
    let last = N - 1;
    for (const b of blacklist) {
      // 如果 b 已经在区间 [sz, N)
      // 可以直接忽略
      if (b >= sz) continue;
      // 跳过所有黑名单中的数字
      while (mapping[last] !== undefined) last--;
      // 将黑名单中的索引映射到合法数字
      mapping[b] = last;
      last--;
    }
    this.mapping = mapping;
  }

  pick() {
    const { sz, mapping } = this;
    // 随机选取一个索引
    const index = Math.floor(Math.random() * sz);
    // 这个索引命中了黑名单，
    // 需要被映射到其他位置
    if (mapping[index] !== undefined) {
      return mapping[index];
    }
    // 若没命中黑名单，则直接返回
    return index;
  }
}

[zhyozhi]

直接生成一个新的 sz 长度的数组非不在黑名单中的数字，空间换时间，简单粗暴。

[saw008]

@zhyozhi 这样的话会发生内存溢出的（Memory Limit Exceeded）

[zhangmuwuge]

是不是吧黑名单的数字给全部交换到最后，然后随机数只取 sz内的 就行了

[David-qiuwenhui]

一、实现随机集合 javascript version

var RandomizedSet = function() {
    // 存储元素的值
    this.nums = new Array();
    // 存储每个元素对应在nums中的索引
    this.indices = new Map();
};

/** 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.insert = function(val) {
    // 若val已存在，不同再插入
    if (this.indices.has(val)) {
        return false;
    }
    // 若val不存在，插入到nums尾部
    // 并记录val对应的索引值，保存到indices
    let index = this.nums.length;
    this.nums.push(val);
    this.indices.set(val, index);
    return true
};

/** 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.remove = function(val) {
    // 若val不存在，不用再删除
    if (!this.indices.has(val)) {
        return false;
    }
    // 先拿到val的索引
    let id = this.indices.get(val);
    // 在nums中将最后一个元素覆盖val
    this.nums[id] = this.nums[this.nums.length - 1];
    // 在indices中更新移动元素的索引值
    this.indices.set(this.nums[id], id);
    // 出栈nums的尾部重复元素
    this.nums.pop();
    // 删除indices中val的索引值
    this.indices.delete(val);
    return true;
};

/**
 * @return {number}
 */
RandomizedSet.prototype.getRandom = function() {
    // 随机获取nums中的元素
    const randomid = Math.floor(Math.random() * this.nums.length);
    return this.nums[randomid];
};

[David-qiuwenhui]

二、避开黑名单的随机数 javascript version

var Solution = function(n, blacklist) {
    // 正常元素的个数
    this.length = n - blacklist.length;
    this.mapping = new Map();
    // 数组最后一个位置的索引指针
    let last = n - 1;

    // 将blacklist元素添加到mapping中
    for (let b of blacklist) {
        this.mapping.set(b, 0);
    }

    // 修改[0, sz)内的blacklist元素映射索引，映射至[sz, n-1]的正常元素索引
    for (let b of blacklist) {
        if (b < this.length) {
            while (this.mapping.has(last)){
                last--;
            }
            // 将blacjlist中的元素索引映射到last
            this.mapping.set(b, last);
            last--;
        }
    }
};

/**
 * @return {number}
 */
Solution.prototype.pick = function() {
    // 随机生成正常的索引值
    var index = Math.floor(Math.random() * this.length);
    // 若该索引值是blacklist中的元素，映射到正常元素
    if (this.mapping.has(index))  {
        return this.mapping.get(index);
    }
    // 若该索引值是blacklist中的元素，返回正常元素的值
    return index;
};

[Yzxsysu]

想问问为什么先put再remove与remove后再put结果会不一样
valToIndex.put(last, index);
valToIndex.remove(val);

[xwxz]

题目一：来一个PHP版本的

class RandomizedSet {
    public $values = [];
    public $indexs = [];

    public function insert($val) {
        if(isset($this->indexs[$val])) {
            return false;
        }

        $this->values[] = $val;
        $this->indexs[$val] = count($this->values) - 1;
        return true;
    }

    public function remove($val) {
        if(!isset($this->indexs[$val])) {
            return false;
        }
        //获取删除元素索引
        $idx = $this->indexs[$val];

        //获取数组末尾元素，用于和删除元素替换
        $lastItem = $this->values[count($this->values)-1];

        //末尾元素的索引更新为删除元素索引
        $this->indexs[$lastItem] = $idx;

        //删除元素索引对应的值修改为末尾元素的值
        $this->values[$idx] = $lastItem;
        $this->values[count($this->values)-1] = $val;//可以不用赋值，反正后面都要删掉的

        //删除末尾元素的值和索引
        array_pop($this->values);
        unset($this->indexs[$val]);
        return true;
    }

    public function getRandom() {
        if(empty($this->values)) {
            return false;
        }
        return $this->values[rand(0,count($this->values) - 1)];
    }
}

[yonggui-yan]

打卡

黑名单，蛮难的呀。
map只存了 需要被映射到其他位置 的index！ 其他位置直接返回index即可。

[AboveParadise]

unsorted_map的count方法不也是O(n)的吗，那这样的插入和删除为什么时间复杂度是O(1)呢

[labuladong]

C++ 的 unordered_map 就是哈希表，其 count 方法复杂度为 O(1)

[NayelyA]

380

type RandomizedSet struct {
    orderMap map[int]int
    nums []int
}


func Constructor() RandomizedSet {
    return RandomizedSet{ map[int]int{},[]int{}}
}


func (this *RandomizedSet) Insert(val int) bool {
    _,ok:=this.orderMap[val]
    if ok {
        return false
    }
    this.orderMap[val] = len(this.nums)
    this.nums = append(this.nums,val)
    return true
}


func (this *RandomizedSet) Remove(val int) bool {

    idx,ok:=this.orderMap[val]
    if !ok{
        return false
    }
    last := len(this.nums) - 1
    //交换
    this.orderMap[this.nums[last]] = idx
    tmp:=this.nums[idx]
    this.nums[idx] = this.nums[last]
    this.nums[last] = tmp
    this.nums = this.nums[:last]
    delete(this.orderMap,val)
    return true 
}


func (this *RandomizedSet) GetRandom() int {
    return this.nums[rand.Intn(len(this.nums))]
}


/**
 * Your RandomizedSet object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Insert(val);
 * param_2 := obj.Remove(val);
 * param_3 := obj.GetRandom();
 */

[marcmk6]

看题解之前憋出来一个版本(不过速度非常慢)：把黑名单里的数字依次映射到一个白名单的数字。就是得用额外变量记录一下白名单，不然重复查找会超时。

from random import randint

class Solution:

    def __init__(self, n: int, blacklist: List[int]):
        balcklist = set(blacklist)

        self.upper = n-1
        self.blacklisted_mapping = dict()

        remapped = 0
        cache = []
        cache_p = 0
        use_cache = False
        for e in blacklist:
            while not use_cache:
                if remapped >= n:
                    use_cache = True
                    break
                elif remapped in blacklist:
                    remapped += 1
                else:
                    break
            if use_cache:
                remapped = cache[cache_p]
                cache_p += 1
                if cache_p == len(cache):
                    cache_p = 0

            self.blacklisted_mapping[e] = remapped
            
            if not use_cache:
                cache.append(remapped)
                remapped += 1

    def pick(self) -> int:
        e = randint(0, self.upper)
        if e in self.blacklisted_mapping:
            return self.blacklisted_mapping[e]
        else:
            return e

[marcmk6]

更大的问题可能是每个白名单数字的概率质量会不相等了

[sunhaotian0122]

对啊，这是我想问的问题，黑名单映射到白名单，那白名单中数随机就不是等概率了啊，除非黑名单数据个数刚好等于白名单

[sunhaotian0122]

哦，又看了下，相当于是把白名单数提前再在整个白名单中随机，是等概率的！

[bruceeewong]

20230110打卡，这映射太巧妙

[zz23333]

710题黑名单数字问题：n=4, blackList=[2,1], 数字2会映射到索引3，数字1会映射到索引0，此时sz=2，随机数只能是0和1，随机到0会直接返回0，随机到1还是会返回0，这样标准答案会判定你的数字不是等概率返回的。
不得已，为了ac，把blackList排了个序，保证黑名单的小数字尽量映射到大的索引

[RomeoFourier]

我有个问题请教下东哥，
我直接生成一个新的 sz=n-bl.length长度的“白名单”数组存储不在黑名单中的数字，空间换时间，结果在运行一个n=1000000000，黑名单长度为1的用例时显示超出内存限制，原因无非是“白名单”数组太长；
但用东哥的方法，同样也要建立一个集合，只不过这个集合的长度是黑名单的长度。
因此我想，如果有一个用例把它反过来，就是说n很大，黑名单也很长，东哥的代码是否也会超出内存呢？

[Jack-cin]

if (b >= sz) {
//这里很关键：如果没有这个，b会吞掉白名单(last)。因为最后rand()%sz;也就是说只在[0，sz)里面取数，取不到b。如果有，last白名单会都留给小于sx的b，这样的话，最后index都会取到所有白名单
//
continue;
}

[Jack-cin]

if (b >= sz) {
//这里很关键：最后的index = rand()%sz已经取不到b（>= sz）了。所以，再建立b->白名单last，只会淹没部分白名单
//
continue;
}

[CarlLy7]

问个问题：

if (mapping.containsKey(index)) {
return mapping.get(index);
}
这里说如果索引找到了黑名单重新映射，这个mapping.get(index)是啥意思，咋映射到别的地方的啊

[CAILeiz]

class RandomizedSet {
  constructor() {
    this.map = new Map();
    this.arr = [];
  }
  insert(val) {
    if (this.map.has(val)) return false;
    this.arr.push(val);
    this.map.set(val, this.arr.length - 1);
    return true;
  }
  remove(val) {
    if (!this.map.has(val)) return false;
    const index = this.map.get(val);
    const last = this.arr.pop();
    this.arr[index] = last;

    return true;
  }
  getRandom() {
    return this.arr[Math.floor(Math.random() * this.arr.length)];
  }
}

[RiverTre]

第27 28行
# 将最后一个元素对应的索引修改为 index
self.valToIndex[self.nums[-1]] = index

请问为什么要先修改哈希表，再交换元素位置啊。把这两行放到29行交换位置之后，为啥会出问题呢？

[RiverTre]

黑名单随机数的前一题。常数时间修改元素这题~

[zhengheng36]

mapping.count 应该为containsKey

[hyros132]

为什么这样会超时呢，感觉复杂度没什么变化。

class Solution {
public:
    int sz;
    unordered_map<int,int> map;
    Solution(int n, vector<int>& blacklist) {
        sz=n-blacklist.size();
        for(auto i:blacklist)
            map[i]=1;
        int last=n-1;
        for(int i=0;i<sz;i++){
            if(map.count(i)){
                while(map.count(last))
                    last--;
                map[i]=last;
                last--;
            }
        }
    }
    
    int pick() {
        int index = rand()%sz;
        if(map.count(index))
            return map[index];
        return index;
    }
};

[simin75simin]

完美主义者可以看https://en.wikipedia.org/wiki/Cuckoo_hashing