LeetCode 710. 黑名单中的随机数
题目描述
题意分析
从
[0,n)中等概率返回一个不在黑名单里的整数，支持多次查询，并尽量减少每次对随机函数的调用。黑名单元素互不重复，且至少留下一个合法数字。值域可能很大，不适合列出全部白名单。可以只随机生成一个紧凑区间内的下标，再将其中不合法的值映射到区间外的合法值，每次查询只调用一次随机整数函数。
解法：紧凑区间随机 + 一一映射
核心思路
[!blue]
设黑名单大小为
B，合法数字总数为m = n-B。先只在低区间[0,m)中均匀抽样，它恰好包含m个随机来源；高区间是[m,n)，不直接参与抽样。假设低区间有
a个黑名单值，那么其中已有m-a个合法值。全部合法值共有m个，所以高区间必然恰好还有a个合法值。这保证可以把低区间的每个黑名单值，分别映射到一个不同的高区间合法值，不会缺少替代目标。预处理时用集合保存黑名单，并让指针
cur从m开始扫描高区间。只处理小于m的黑名单值：先跳过cur遇到的黑名单位置，再把当前合法值分配为映射目标，随后增加cur。指针只向前走，所以目标不会重复；高区间黑名单本来就不可能被直接抽到，无需建立映射。查询先均匀生成
x，满足0 <= x < m。若x在映射中，返回它的目标，否则返回x自身。低区间的合法值各自只由自己产生；高区间的合法值各自由唯一一个低区间黑名单值产生，两组结果也不会相交。因此每个合法数字恰好拥有一个随机来源，其概率都是1/m。题目保证
m >= 1，随机区间不会为空。黑名单为空时不需要任何映射，算法自然变成在整个[0,n)中均匀抽样。
解题步骤
- 计算
m = n-blacklist.length，将全部黑名单值放入集合。- 初始化高区间指针
cur = m。- 遍历黑名单，只为小于
m的值建立映射；每次跳过高区间黑名单后，分配一个尚未使用的合法目标。pick调用一次随机函数，在[0,m)中得到x。- 存在映射就返回对应目标，否则直接返回
x。
代码实现
class Solution {
private final int m;
private final Map<Integer, Integer> mp = new HashMap<>();
private final Random rand = new Random();
public Solution(int n, int[] blacklist) {
this.m = n - blacklist.length;
Set<Integer> black = new HashSet<>();
for (int b : blacklist) {
black.add(b);
}
int cur = m;
for (int b : blacklist) {
// 高区间不参与随机抽样，只需映射低区间的黑名单值。
if (b >= m) {
continue;
}
while (black.contains(cur)) {
cur++;
}
// 每个低区间黑名单值对应一个不同的高区间白名单值。
mp.put(b, cur);
cur++;
}
}
public int pick() {
int x = rand.nextInt(m);
return mp.getOrDefault(x, x);
}
}
import "math/rand"
type Solution struct {
m int
mp map[int]int
}
func Constructor(n int, blacklist []int) Solution {
m := n - len(blacklist)
black := make(map[int]struct{}, len(blacklist))
for _, b := range blacklist {
black[b] = struct{}{}
}
mp := make(map[int]int)
cur := m
for _, b := range blacklist {
// 高区间不参与随机抽样，只需映射低区间的黑名单值。
if b >= m {
continue
}
for {
if _, ok := black[cur]; !ok {
break
}
cur++
}
// 每个低区间黑名单值对应一个不同的高区间白名单值。
mp[b] = cur
cur++
}
return Solution{m: m, mp: mp}
}
func (s *Solution) Pick() int {
x := rand.Intn(s.m)
if v, ok := s.mp[x]; ok {
return v
}
return x
}
复杂度分析
- 时间复杂度：预处理期望 $O(B+1)$。建立集合和遍历黑名单各为线性，高区间总长度就是
B，指针在所有映射过程中合计也只走线性步数。每次查询期望 $O(1)$，只随机生成一次并做一次哈希查找。- 空间复杂度：$O(B+1)$。预处理黑名单集合和映射占线性空间，查询阶段只需保留映射，无需展开大小可能为
n的全部值域。
关键点总结
[!green]
- 随机来源区间的长度等于合法数字总数，低段缺少的合法值恰好由高段补齐。
- 映射必须使用不同的合法目标，一一对应才保证所有结果等概率。
- 高区间从不直接参与抽样，不会与被映射到这里的结果形成重复来源。
- 黑名单不必排序，高区间指针的单向扫描已经保证映射目标互不重复。
易错点总结
[!yellow]
- 仍从
[0,n)抽样再套用映射，会让部分高区间合法值同时拥有直接来源和映射来源，产生概率偏差。- 把多个低区间黑名单值映射到同一个目标，会让那个目标更容易被选中。
- 高区间指针不跳过黑名单，可能映射到禁止返回的值。
- 使用包含
m的随机区间，会多出不属于设计范围的随机来源。- 为每次查询重新寻找可用替代值，会浪费预处理结果，也可能破坏固定的一一对应关系。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 380. O(1) 时间插入、删除和获取随机元素 | 中等 | 原题维护动态紧凑数组后按下标均匀抽样，本题值域巨大且黑名单静态，不能展开全部合法值。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！