LeetCode 题解工作台
黑名单中的随机数
给定一个整数 n 和一个 无重复 黑名单整数数组 blacklist 。设计一种算法，从 [0, n - 1] 范围内的任意整数中选取一个 未加入 黑名单 blacklist 的整数。任何在上述范围内且不在黑名单 blacklist 中的整数都应该有 同等的可能性 被返回。 优化你的算法，使它最小化…
6
题型
4
代码语言
3
相关题
当前训练重点
困难 · 数组·哈希·扫描
答案摘要
class Solution: def __init__(self, n: int, blacklist: List[int]):
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给定一个整数 n 和一个 无重复 黑名单整数数组 blacklist 。设计一种算法，从 [0, n - 1] 范围内的任意整数中选取一个 未加入 黑名单 blacklist 的整数。任何在上述范围内且不在黑名单 blacklist 中的整数都应该有 同等的可能性 被返回。
优化你的算法，使它最小化调用语言 内置 随机函数的次数。
实现 Solution 类:
Solution(int n, int[] blacklist)初始化整数n和被加入黑名单blacklist的整数int pick()返回一个范围为[0, n - 1]且不在黑名单blacklist中的随机整数
示例 1：
输入
["Solution", "pick", "pick", "pick", "pick", "pick", "pick", "pick"]
[[7, [2, 3, 5]], [], [], [], [], [], [], []]
输出
[null, 0, 4, 1, 6, 1, 0, 4]
解释
Solution solution = new Solution(7, [2, 3, 5]);
solution.pick(); // 返回0，任何[0,1,4,6]的整数都可以。注意，对于每一个pick的调用，
// 0、1、4和6的返回概率必须相等(即概率为1/4)。
solution.pick(); // 返回 4
solution.pick(); // 返回 1
solution.pick(); // 返回 6
solution.pick(); // 返回 1
solution.pick(); // 返回 0
solution.pick(); // 返回 4
提示:
1 <= n <= 1090 <= blacklist.length <= min(105, n - 1)0 <= blacklist[i] < nblacklist中所有值都 不同-
pick最多被调用2 * 104次
解题思路
方法一：哈希表
class Solution:
def __init__(self, n: int, blacklist: List[int]):
self.k = n - len(blacklist)
self.d = {}
i = self.k
black = set(blacklist)
for b in blacklist:
if b < self.k:
while i in black:
i += 1
self.d[b] = i
i += 1
def pick(self) -> int:
x = randrange(self.k)
return self.d.get(x, x)
# Your Solution object will be instantiated and called as such:
# obj = Solution(n, blacklist)
# param_1 = obj.pick()
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(1) per pick after O(B) preprocessing where B is the blacklist length. Space complexity is O(B) for the hash map storing remapped values. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Emphasize minimizing random function calls while ensuring uniform distribution.
- question_mark
Check if the candidate maps blacklisted indices correctly instead of scanning every time.
- question_mark
Look for clear reasoning on hash map usage and upper-lower range mapping.
常见陷阱
外企场景- error
Attempting to randomly pick and retry until valid, which is inefficient for large n and blacklist.
- error
Not mapping blacklisted numbers that fall in the random pick range, leading to incorrect probabilities.
- error
Overusing space by mapping all blacklist numbers instead of only those needed for O(1) access.
进阶变体
外企场景- arrow_right_alt
Pick multiple random integers without replacement while respecting the blacklist.
- arrow_right_alt
Blacklist is dynamic and can change between picks, requiring dynamic remapping.
- arrow_right_alt
Support weighted random picks among non-blacklisted numbers instead of uniform selection.