常数时间删除-查找数组中的任意元素
数据结构精品课 已更新到 V2.1， 手把手刷二叉树系列课程 上线。
| LeetCode | 力扣 | 难度 |
|---|---|---|
| 380. Insert Delete GetRandom O(1) | 380. O(1) 时间插入、删除和获取随机元素 | 🟠 |
| 710. Random Pick with Blacklist | 710. 黑名单中的随机数 | 🔴 |
| - | 剑指 Offer II 030. 插入、删除和随机访问都是 O(1) 的容器 | 🟠 |
———–
本文有视频版： 动手实现哈希数组。
这些问题的一个技巧点在于，如何结合哈希表和数组，使得数组的删除操作时间复杂度也变成 O(1)？下面来一道道看。
实现随机集合
这是力扣第 380 题「 常数时间插入、删除和获取随机元素」，看下题目：
就是让我们实现如下一个类：
// 注意：java 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 cpp 代码对比查看。
class RandomizedSet {
/** 如果 val 不存在集合中，则插入并返回 true，否则直接返回 false */
public boolean insert(int val) {}
/** 如果 val 在集合中，则删除并返回 true，否则直接返回 false */
public boolean remove(int val) {}
/** 从集合中等概率地随机获得一个元素 */
public int getRandom() {}
}
class RandomizedSet {
public:
/** 如果 val 不存在集合中，则插入并返回 true，否则直接返回 false */
bool insert(int val) {}
/** 如果 val 在集合中，则删除并返回 true，否则直接返回 false */
bool remove(int val) {}
/** 从集合中等概率地随机获得一个元素 */
int getRandom() {}
}
# 注意：python 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 cpp 代码对比查看。
class RandomizedSet:
"""
如果 val 不存在集合中，则插入并返回 true，否则直接返回 false
"""
def insert(self, val: int) -> bool:
"""
如果 val 在集合中，则删除并返回 true，否则直接返回 false
"""
def remove(self, val: int) -> bool:
"""
从集合中等概率地随机获得一个元素
"""
def getRandom(self) -> int:
// 注意：go 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 cpp 代码对比查看。
type RandomizedSet struct {
}
/** 如果 val 不存在集合中，则插入并返回 true，否则直接返回 false */
func (this *RandomizedSet) Insert(val int) bool {
}
/** 如果 val 在集合中，则删除并返回 true，否则直接返回 false */
func (this *RandomizedSet) Remove(val int) bool {
}
/** 从集合中等概率地随机获得一个元素 */
func (this *RandomizedSet) GetRandom() int {
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 cpp 代码对比查看。
/**
* Initialize your data structure here.
* 构造函数
*/
var RandomizedSet = function() {
this.map = new Map(); // map 存储元素到下标的映射
this.array = []; // 数组用于 O(1) 随机获取元素
};
/**
* Inserts a value to the set. Returns true iff the set did not already contain the specified element.
* 向集合中插入指定元素 val。
* 返回值表示集合是否已经包含了该元素
*/
RandomizedSet.prototype.insert = function(val) {
if (this.map.has(val)) {
return false;
}
this.map.set(val, this.array.length);
this.array.push(val);
return true;
};
/**
* Removes a value from the set. Returns true iff the set contained the specified element.
* 从集合中删除指定元素 val。
* 返回值表示集合是否包含该元素
*/
RandomizedSet.prototype.remove = function(val) {
if (!this.map.has(val)) {
return false;
}
const index = this.map.get(val);
const last = this.array[this.array.length - 1];
this.array[index] = last;
this.array.pop();
this.map.set(last, index);
this.map.delete(val);
return true;
};
/**
* Get a random element from the set.
* 从集合中等概率地随机获取一个元素
*/
RandomizedSet.prototype.getRandom = function() {
const index = Math.floor(Math.random() * this.array.length);
return this.array[index];
};
本题的难点在于两点：
1、插入，删除，获取随机元素这三个操作的时间复杂度必须都是 O(1)。
2、getRandom 方法返回的元素必须等概率返回随机元素，也就是说，如果集合里面有 n 个元素，每个元素被返回的概率必须是 1/n。
我们先来分析一下：对于插入，删除，查找这几个操作，哪种数据结构的时间复杂度是 O(1)？
HashSet 肯定算一个对吧。哈希集合的底层原理就是一个大数组，我们把元素通过哈希函数映射到一个索引上；如果用拉链法解决哈希冲突，那么这个索引可能连着一个链表或者红黑树。
那么请问对于这样一个标准的 HashSet，你能否在 O(1) 的时间内实现 getRandom 函数？
其实是不能的，因为根据刚才说到的底层实现，元素是被哈希函数「分散」到整个数组里面的，更别说还有拉链法等等解决哈希冲突的机制，所以做不到 O(1) 时间「等概率」随机获取元素。
除了 HashSet，还有一些类似的数据结构，比如哈希链表 LinkedHashSet，我们后文
手把手实现LRU算法 和
手把手实现LFU算法 讲过这类数据结构的实现原理，本质上就是哈希表配合双链表，元素存储在双链表中。
但是，LinkedHashSet 只是给 HashSet 增加了有序性，依然无法按要求实现我们的 getRandom 函数，因为底层用链表结构存储元素的话，是无法在 O(1) 的时间内访问某一个元素的。
根据上面的分析，对于 getRandom 方法，如果想「等概率」且「在 O(1) 的时间」取出元素，一定要满足：底层用数组实现，且数组必须是紧凑的。
这样我们就可以直接生成随机数作为索引，从数组中取出该随机索引对应的元素，作为随机元素。
但如果用数组存储元素的话，插入，删除的时间复杂度怎么可能是 O(1) 呢？
可以做到！对数组尾部进行插入和删除操作不会涉及数据搬移，时间复杂度是 O(1)。
所以，如果我们想在 O(1) 的时间删除数组中的某一个元素 val，可以先把这个元素交换到数组的尾部，然后再 pop 掉。
交换两个元素必须通过索引进行交换对吧，那么我们需要一个哈希表 valToIndex 来记录每个元素值对应的索引。
有了思路铺垫，我们直接看代码：
// 注意：java 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 cpp 代码对比查看。
class RandomizedSet {
// 存储元素的值
List<Integer> nums;
// 记录每个元素对应在 nums 中的索引
Map<Integer, Integer> valToIndex;
public RandomizedSet() {
nums = new ArrayList<>();
valToIndex = new HashMap<>();
}
public boolean insert(int val) {
// 若 val 已存在，不用再插入
if (valToIndex.containsKey(val)) {
return false;
}
// 若 val 不存在，插入到 nums 尾部，
// 并记录 val 对应的索引值
valToIndex.put(val, nums.size());
nums.add(val);
return true;
}
public boolean remove(int val) {
// 若 val 不存在，不用再删除
if (!valToIndex.containsKey(val)) {
return false;
}
// 先拿到 val 的索引
int index = valToIndex.get(val);
// 将最后一个元素对应的索引修改为 index
valToIndex.put(nums.get(nums.size() - 1), index);
// 交换 val 和最后一个元素
Collections.swap(nums, index, nums.size() - 1);
// 在数组中删除元素 val
nums.remove(nums.size() - 1);
// 删除元素 val 对应的索引
valToIndex.remove(val);
return true;
}
public int getRandom() {
// 随机获取 nums 中的一个元素
return nums.get((int) (Math.random() * nums.size()));
}
}
class RandomizedSet {
public:
// 存储元素的值
vector<int> nums;
// 记录每个元素对应在 nums 中的索引
unordered_map<int,int> valToIndex;
bool insert(int val) {
// 若 val 已存在，不用再插入
if (valToIndex.count(val)) {
return false;
}
// 若 val 不存在，插入到 nums 尾部，
// 并记录 val 对应的索引值
valToIndex[val] = nums.size();
nums.push_back(val);
return true;
}
bool remove(int val) {
// 若 val 不存在，不用再删除
if (!valToIndex.count(val)) {
return false;
}
// 先拿到 val 的索引
int index = valToIndex[val];
// 将最后一个元素对应的索引修改为 index
valToIndex[nums.back()] = index;
// 交换 val 和最后一个元素
swap(nums[index], nums.back());
// 在数组中删除元素 val
nums.pop_back();
// 删除元素 val 对应的索引
valToIndex.erase(val);
return true;
}
int getRandom() {
// 随机获取 nums 中的一个元素
return nums[rand() % nums.size()];
}
};
# 注意：python 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 cpp 代码对比查看。
import random
class RandomizedSet:
def __init__(self):
self.nums = [] # 存储元素的值
self.valToIndex = {} # 记录每个元素对应在 nums 中的索引
def insert(self, val: int) -> bool:
# 若 val 已存在，不用再插入
if val in self.valToIndex:
return False
# 若 val 不存在，插入到 nums 尾部，
# 并记录 val 对应的索引值
self.valToIndex[val] = len(self.nums)
self.nums.append(val)
return True
def remove(self, val: int) -> bool:
# 若 val 不存在，不用再删除
if val not in self.valToIndex:
return False
# 先拿到 val 的索引
index = self.valToIndex[val]
# 将最后一个元素对应的索引修改为 index
self.valToIndex[self.nums[-1]] = index
# 交换 val 和最后一个元素
self.nums[index], self.nums[-1] = self.nums[-1], self.nums[index]
# 在数组中删除元素 val
self.nums.pop()
# 删除元素 val 对应的索引
del self.valToIndex[val]
return True
def getRandom(self) -> int:
# 随机获取 nums 中的一个元素
return random.choice(self.nums)
// 注意：go 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 cpp 代码对比查看。
type RandomizedSet struct {
nums []int // 存储元素的值
valToIndex map[int]int // 记录每个元素对应在 nums 中的索引
}
func Constructor() RandomizedSet {
return RandomizedSet{
nums: []int{},
valToIndex: make(map[int]int),
}
}
func (this *RandomizedSet) Insert(val int) bool {
// 若 val 已存在，不用再插入
if _, ok := this.valToIndex[val]; ok {
return false
}
// 若 val 不存在，插入到 nums 尾部，
// 并记录 val 对应的索引值
this.valToIndex[val] = len(this.nums)
this.nums = append(this.nums, val)
return true
}
func (this *RandomizedSet) Remove(val int) bool {
// 若 val 不存在，不用再删除
if _, ok := this.valToIndex[val]; !ok {
return false
}
// 先拿到 val 的索引
index := this.valToIndex[val]
// 将最后一个元素对应的索引修改为 index
this.valToIndex[this.nums[len(this.nums) - 1]] = index
// 交换 val 和最后一个元素
this.nums[index], this.nums[len(this.nums) - 1] = this.nums[len(this.nums) - 1], this.nums[index]
// 在数组中删除元素 val
this.nums = this.nums[:len(this.nums) - 1]
// 删除元素 val 对应的索引
delete(this.valToIndex, val)
return true
}
func (this *RandomizedSet) GetRandom() int {
// 随机获取 nums 中的一个元素
return this.nums[rand.Intn(len(this.nums))]
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 cpp 代码对比查看。
var RandomizedSet = function() {
// 存储元素的值
this.nums = [];
// 记录每个元素对应在 nums 中的索引
this.valToIndex = {};
};
RandomizedSet.prototype.insert = function(val) {
// 若 val 已存在，不用再插入
if (this.valToIndex[val] !== undefined) {
return false;
}
// 若 val 不存在，插入到 nums 尾部，
// 并记录 val 对应的索引值
this.valToIndex[val] = this.nums.length;
this.nums.push(val);
return true;
};
RandomizedSet.prototype.remove = function(val) {
// 若 val 不存在，不用再删除
if (this.valToIndex[val] === undefined) {
return false;
}
// 先拿到 val 的索引
var index = this.valToIndex[val];
// 将最后一个元素对应的索引修改为 index
this.valToIndex[this.nums[this.nums.length-1]] = index;
// 交换 val 和最后一个元素
[this.nums[index], this.nums[this.nums.length-1]] = [this.nums[this.nums.length-1], this.nums[index]];
// 在数组中删除元素 val
this.nums.pop();
// 删除元素 val 对应的索引
delete this.valToIndex[val];
return true;
};
RandomizedSet.prototype.getRandom = function() {
// 随机获取 nums 中的一个元素
return this.nums[Math.floor(Math.random() * this.nums.length)];
};
注意 remove(val) 函数，对 nums 进行插入、删除、交换时，都要记得修改哈希表 valToIndex，否则会出现错误。
至此，这道题就解决了，每个操作的复杂度都是 O(1)，且随机抽取的元素概率是相等的。
避开黑名单的随机数
有了上面一道题的铺垫，我们来看一道更难一些的题目，力扣第 710 题「 黑名单中的随机数」，我来描述一下题目：
给你输入一个正整数 N，代表左闭右开区间 [0,N)，再给你输入一个数组 blacklist，其中包含一些「黑名单数字」，且 blacklist 中的数字都是区间 [0,N) 中的数字。
现在要求你设计如下数据结构：
// 注意：java 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 cpp 代码对比查看。
class Solution {
// 构造函数，输入参数 N 和 blacklist
public Solution(int N, List<Integer> blacklist) {
}
// 在区间 [0,N) 中等概率随机选取一个元素并返回
// 这个元素不能是 blacklist 中的元素
public int pick() {
}
}
class Solution {
public:
// 构造函数，输入参数
Solution(int N, vector<int>& blacklist) {}
// 在区间 [0,N) 中等概率随机选取一个元素并返回
// 这个元素不能是 blacklist 中的元素
int pick() {}
};
# 注意：python 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 cpp 代码对比查看。
class Solution:
def __init__(self, N: int, blacklist: List[int]):
"""
:param N: 元素总数
:param blacklist: 不能被选的黑名单列表
"""
pass
def pick(self) -> int:
"""
:return: 等概率随机选取但不能是黑名单中的元素
"""
pass
// 注意：go 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 cpp 代码对比查看。
type Solution struct {
//构造函数，输入参数
N int
blacklist []int
}
// 在区间 [0,N) 中等概率随机选取一个元素并返回
// 这个元素不能是 blacklist 中的元素
func (this *Solution) Pick() int {}
// 注意：javascript 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 cpp 代码对比查看。
var Solution = function(N, blacklist) {
// 构造函数，输入参数
};
Solution.prototype.pick = function() {
// 在区间 [0,N) 中等概率随机选取一个元素并返回
// 这个元素不能是 blacklist 中的元素
};
pick 函数会被多次调用，每次调用都要在区间 [0,N) 中「等概率随机」返回一个「不在 blacklist 中」的整数。
这应该不难理解吧，比如给你输入 N = 5, blacklist = [1,3]，那么多次调用 pick 函数，会等概率随机返回 0, 2, 4 中的某一个数字。
而且题目要求，在 pick 函数中应该尽可能少调用随机数生成函数 rand()。
这句话什么意思呢，比如说我们可能想出如下拍脑袋的解法：
int pick() {
int res = rand() % N;
while (res exists in blacklist) {
// 重新随机一个结果
res = rand() % N;
}
return res;
}
这个函数会多次调用 rand() 函数，执行效率竟然和随机数相关，不是一个漂亮的解法。
聪明的解法类似上一道题，我们可以将区间 [0,N) 看做一个数组，然后将 blacklist 中的元素移到数组的最末尾，同时用一个哈希表进行映射：
根据这个思路，我们可以写出第一版代码（还存在几处错误）：
// 注意：java 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 cpp 代码对比查看。
/**
* 根据黑名单生成的随机数
*/
class Solution {
// 最终数组中的元素个数
int sz;
// mapping 用于记录哪些黑名单索引需要被替换成白名单索引
HashMap<Integer, Integer> mapping;
/**
* 构造函数，时间复杂度 O(n)
*
* @param N 最终数组中的元素个数
* @param blacklist 黑名单中的元素索引集合
*/
public Solution(int N, int[] blacklist) {
sz = N - blacklist.length;
int last = N - 1;
mapping = new HashMap<>();
for (int b : blacklist) {
mapping.put(b, last);
last--;
}
}
/**
* 获取随机数，时间复杂度 O(logn)
*
* @return 随机数
*/
public int pick() {
int index = (int) (Math.random() * sz);
if (mapping.containsKey(index)) {
return mapping.get(index);
}
return index;
}
}
class Solution {
public:
int sz;
unordered_map<int, int> mapping;
Solution(int N, vector<int>& blacklist) {
// 最终数组中的元素个数
sz = N - blacklist.size();
// 最后一个元素的索引
int last = N - 1;
// 将黑名单中的索引换到最后去
for (int b : blacklist) {
mapping[b] = last;
last--;
}
}
// 后文实现
int pick() {}
};
# 注意：python 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 cpp 代码对比查看。
from typing import List
class Solution:
def __init__(self, N: int, blacklist: List[int]):
# 最终数组中的元素个数
self.sz = N - len(blacklist)
self.mapping = {}
# 最后一个元素的索引
last = N - 1
# 将黑名单中的索引换到最后去
for b in blacklist:
self.mapping[b] = last
last -= 1
# 后文实现
def pick(self) -> int:
pass
// 注意：go 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 cpp 代码对比查看。
type Solution struct {
sz int // 数组中剩余的元素个数
mapping map[int]int // 将黑名单中的元素映射成白名单中的元素
}
// 构造函数，需要传入 N 和 blacklist
func Constructor(N int, blacklist []int) Solution {
// 最终数组中的元素个数
sz := N - len(blacklist)
// 将黑名单中的索引换到最后去，对应着白名单中的元素
mapping := make(map[int]int)
last := N - 1
for _, b := range blacklist {
mapping[b] = last
last--
}
return Solution{sz:sz, mapping:mapping}
}
//获取一个随机的白名单中的元素
func (this *Solution) Pick() int {
//to be implemented
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 cpp 代码对比查看。
// 定义 Solution 类
var Solution = function(N, blacklist) {
// 存储黑名单中的数值和最后一个位置之间的映射
this.mapping = new Map();
// 最终数组中的元素个数，初始值设为 N 减去黑名单中元素的数量
this.sz = N - blacklist.length;
// 最后一个元素的索引
var last = N - 1;
// 将黑名单中的索引换到最后去
for (var i = 0; i < blacklist.length; i++) {
this.mapping.set(blacklist[i], last);
last--;
}
};
// 实现 pick() 函数
Solution.prototype.pick = function() {
// implementation
};
如上图，相当于把黑名单中的数字都交换到了区间 [sz, N) 中，同时把 [0, sz) 中的黑名单数字映射到了正常数字。
根据这个逻辑，我们可以写出 pick 函数：
int pick() {
// 随机选取一个索引
int index = rand() % sz;
// 这个索引命中了黑名单，
// 需要被映射到其他位置
if (mapping.count(index)) {
return mapping[index];
}
// 若没命中黑名单，则直接返回
return index;
}
这个 pick 函数已经没有问题了，但是构造函数还有两个问题。
第一个问题，如下这段代码：
int last = N - 1;
// 将黑名单中的索引换到最后去
for (int b : blacklist) {
mapping[b] = last;
last--;
}
我们将黑名单中的 b 映射到 last，但是我们能确定 last 不在 blacklist 中吗？
比如下图这种情况，我们的预期应该是 1 映射到 3，但是错误地映射到 4：
在对 mapping[b] 赋值时，要保证 last 一定不在 blacklist 中，可以如下操作：
// 构造函数
Solution(int N, vector<int>& blacklist) {
sz = N - blacklist.size();
// 先将所有黑名单数字加入 map
for (int b : blacklist) {
// 这里赋值多少都可以
// 目的仅仅是把键存进哈希表
// 方便快速判断数字是否在黑名单内
mapping[b] = 666;
}
int last = N - 1;
for (int b : blacklist) {
// 跳过所有黑名单中的数字
while (mapping.count(last)) {
last--;
}
// 将黑名单中的索引映射到合法数字
mapping[b] = last;
last--;
}
}
第二个问题，如果 blacklist 中的黑名单数字本身就存在区间 [sz, N) 中，那么就没必要在 mapping 中建立映射，比如这种情况：
我们根本不用管 4，只希望把 1 映射到 3，但是按照 blacklist 的顺序，会把 4 映射到 3，显然是错误的。
我们可以稍微修改一下，写出正确的解法代码：
// 注意：java 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 cpp 代码对比查看。
class Solution {
int sz;
Map<Integer, Integer> mapping;
public Solution(int N, int[] blacklist) {
sz = N - blacklist.length;
mapping = new HashMap<>();
for (int b : blacklist) {
mapping.put(b, 666);
}
int last = N - 1;
for (int b : blacklist) {
// 如果 b 已经在区间 [sz, N)
// 可以直接忽略
if (b >= sz) {
continue;
}
while (mapping.containsKey(last)) {
last--;
}
mapping.put(b, last);
last--;
}
}
public int pick() {
// 随机选取一个索引
int index = (int)(Math.random() * sz);
// 这个索引命中了黑名单，
// 需要被映射到其他位置
if (mapping.containsKey(index)) {
return mapping.get(index);
}
// 若没命中黑名单，则直接返回
return index;
}
}
class Solution {
public:
int sz;
unordered_map<int, int> mapping;
Solution(int N, vector<int>& blacklist) {
sz = N - blacklist.size();
for (int b : blacklist) {
mapping[b] = 666;
}
int last = N - 1;
for (int b : blacklist) {
// 如果 b 已经在区间 [sz, N)
// 可以直接忽略
if (b >= sz) {
continue;
}
while (mapping.count(last)) {
last--;
}
mapping[b] = last;
last--;
}
}
int pick() {
// 随机选取一个索引
int index = rand() % sz;
// 这个索引命中了黑名单，
// 需要被映射到其他位置
if (mapping.count(index)) {
return mapping[index];
}
// 若没命中黑名单，则直接返回
return index;
}
};
# 注意：python 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 cpp 代码对比查看。
from typing import List
import random
class Solution:
def __init__(self, N: int, blacklist: List[int]):
# 计算真实的数据个数
self.sz = N - len(blacklist)
# 用哈希表记录黑名单中的数据
self.mapping = {}
for b in blacklist:
self.mapping[b] = 666
# 处理黑名单中的数据，将其映射到其他位置
last = N - 1
for b in blacklist:
if b >= self.sz:
continue
# 找到一个未被映射到的位置，将其作为映射目标
while last in self.mapping:
last -= 1
# 将 b 映射到 last，并将 last 位置的数据映射到 b
self.mapping[b] = last
last -= 1
def pick(self) -> int:
# 随机生成一个索引
index = random.randint(0, self.sz - 1)
# 如果该索引对应的数据在黑名单中，返回其映射到的数据
if index in self.mapping:
return self.mapping[index]
# 否则直接返回该索引
return index
// 注意：go 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 cpp 代码对比查看。
type Solution struct {
sz int
mapping map[int]int
}
func Constructor(N int, blacklist []int) Solution {
sz := N - len(blacklist)
mapping := make(map[int]int)
last := N - 1
for _, b := range blacklist {
// 如果黑名单中的数已经在区间 [sz, N) 中，
// 则直接忽略它
if b >= sz {
mapping[b] = 666
continue
}
// 寻找一个不在黑名单中的位置 last
for _, exists := mapping[last]; exists; _, exists = mapping[last] {
last--
}
// 将 b 映射到 last，并将 last 减一
mapping[b] = last
last--
}
return Solution{sz: sz, mapping: mapping}
}
func (this *Solution) Pick() int {
// 随机选取一个索引
index := rand.Intn(this.sz)
// 如果 index 命中了黑名单中的数，
// 则返回它被映射到的那个位置
if val, ok := this.mapping[index]; ok {
return val
}
// 如果 index 没命中黑名单，则直接返回
return index
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 cpp 代码对比查看。
var Solution = function(N, blacklist) {
this.sz = N - blacklist.length;
this.mapping = {};
for (let b of blacklist) {
this.mapping[b] = 666;
}
let last = N - 1;
for (let b of blacklist) {
// 如果 b 已经在区间 [sz, N)
// 可以直接忽略
if (b >= this.sz) {
continue;
}
while (this.mapping[last]) {
last--;
}
this.mapping[b] = last;
last--;
}
};
Solution.prototype.pick = function() {
// 随机选取一个索引
let index = Math.floor(Math.random() * this.sz);
// 这个索引命中了黑名单，
// 需要被映射到其他位置
if (this.mapping[index]) {
return this.mapping[index];
}
// 若没命中黑名单，则直接返回
return index;
};
至此，这道题也解决了，总结一下本文的核心思想：
1、如果想高效地，等概率地随机获取元素，就要使用数组作为底层容器。
2、如果要保持数组元素的紧凑性，可以把待删除元素换到最后，然后 pop 掉末尾的元素，这样时间复杂度就是 O(1) 了。当然，我们需要额外的哈希表记录值到索引的映射。
3、对于第二题，数组中含有「空洞」（黑名单数字），也可以利用哈希表巧妙处理映射关系，让数组在逻辑上是紧凑的，方便随机取元素。
本文就到这里，更多数据结构设计相关的题目参见 数据结构设计经典习题。
引用本文的题目
安装 我的 Chrome 刷题插件 点开下列题目可直接查看解题思路：
| LeetCode | 力扣 |
|---|---|
| 519. Random Flip Matrix | 519. 随机翻转矩阵 |
| - | 剑指 Offer II 030. 插入、删除和随机访问都是 O(1) 的容器 |
引用本文的文章
＿＿＿＿＿＿＿＿＿＿＿＿＿
《labuladong 的算法小抄》已经出版，关注公众号查看详情；后台回复关键词「进群」可加入算法群；回复「全家桶」可下载配套 PDF 和刷题全家桶：
共同维护高质量学习环境，评论礼仪见这里，违者直接拉黑不解释