概率题是面试从「你会不会写代码」切换到「你到底懂不懂自己写的代码」的分水岭。这里没有数据结构要背——只有几个动作(扩大取值范围、拒绝多余部分、原地交换),外加一条不可打折的义务:把「每个结果等概率」当场证明出来。作为系列的最后一课,我们走一遍经典全集——用有偏硬币造公平硬币、用 rand5 造 rand7(以及 Rand10 from Rand7)、用一个随机 bit 造任意范围、唯一正确的洗牌算法、面对无法存下的数据流做蓄水池抽样、加权随机选择——并以面试官最爱的收尾杀招结束:「现在不许调用任何随机函数,实现 random()。」
- 拒绝采样是万能钥匙——当一个随机源「盖过」了你的目标范围,就保留落在范围内的值、把多余的重摇。这里几乎每道题都是「先扩大,再拒绝」的变体。
- 有偏硬币造公平硬币——抛两次;
10 → 1、01 → 0,抛出11/00就重来。因为P(10) = P(01) = p(1−p),偏差被精确抵消(von Neumann 技巧)。 - 要组合,不要相加——
rand5*5 + rand5是均匀的rand25(base-5 数位);随机 bit 能拼出任意范围。两次调用相加是三角分布,不是均匀——经典陷阱。 - 洗牌只认 Fisher–Yates——把位置
i和[i, n)里的随机下标交换。天真的「和任意下标交换」会产生有偏排列。O(n),原地。 - 蓄水池抽样——从长度未知的数据流里等概率抽样:第 n 个到达者以
k/n的概率抢下槽位。一遍扫描,O(k) 空间。 - 加权抽取 = 前缀和 + 二分——把权重铺在累积数轴上,取一个均匀值,二分定位落在哪个桶。每次抽取 O(log n)(LC 528)。
随机化题几乎都能归结为两个动作:扩大——把一个小的均匀源撑成更大的(数位、bit 或乘积);拒绝——把多出来的尾巴丢掉重摇,让留下来的仍然均匀。在这之上叠三个可复用套路:Fisher–Yates 做排列、reservoir sampling 做数据流、前缀和 + 二分做加权选择。搞懂每一个为什么保持均匀,你就能在白板上现推其余。
两个基本件:均匀区间与拒绝采样
在任何有名字的算法之前,先钉死这节课处处依赖的两个积木。第一个是生成一个均匀整数。Java 里有两种写法,而且面试官确实会留意你顺手选了哪一种:
// [0, k): Math.random() 返回 [0, 1) 的 double
int a = (int) (Math.random() * k); // 注意括号——要 cast 乘积,不是只 cast Math.random()
// [0, k): 更地道的写法——完全不碰浮点
Random random = new Random();
int b = random.nextInt(k); // [0, k) 均匀
// 闭区间 [min, max]
int c = min + (int) (Math.random() * ((max - min) + 1));(int)(Math.random() * k) 的括号很关键:(int) Math.random() * k 会先把 [0,1) 的 double cast 成 0,结果恒为零。能用就优先 Random.nextInt(k)——它彻底不碰浮点,对均匀性也更诚实。
第二个基本件是拒绝采样(rejection sampling),也是本课最重要的一个想法。配方:先造一个盖过目标范围的均匀源,再把落在干净子区间之外的值全部丢弃、重摇。只要被接受的区域恰好是目标范围的整数份拷贝,每个目标值就等概率。代价是几次浪费的摇动;回报是可证的均匀性。下面的 Q1、Q2、Q3 全都是穿了不同外衣的拒绝采样。
有偏硬币造公平硬币
热身题:给你一枚正面概率 p、反面概率 1 − p 的硬币,p 未知且不等于 0.5,请造出一个公平的 50/50 bit。加一个修正常数是不可能的——你根本不知道 p。诀窍是找到两个无论 p 是多少都保证等概率的事件。抛两次,看这一对:
| 两次抛掷 | 概率 | 动作 |
|---|---|---|
| 1 1 | p · p | 丢弃,重来 |
| 1 0 | p · (1 − p) | 返回 1 |
| 0 1 | (1 − p) · p | 返回 0 |
| 0 0 | (1 − p) · (1 − p) | 丢弃,重来 |
两个混合结果 10 和 01 的概率完全相同,都是 p(1−p)——不对称被抵消了。于是把 10 映射成一个结果、01 映射成另一个;两次一致(11 或 00)时拒绝、从头再来。这就是拒绝采样最纯粹的两结果形式,人称 von Neumann 技巧。
// toss() 以概率 p 返回 1,以 1-p 返回 0 (p 未知,p != 0.5)
public int fairToss() {
int t1 = toss();
int t2 = toss();
if (t1 == 1 && t2 == 0) return 1; // P = p(1-p)
if (t1 == 0 && t2 == 1) return 0; // P = (1-p)p — 相等,偏差抵消
return fairToss(); // 11 或 00 → 拒绝并重来
}递归以概率 1 终止:每一对抛掷以 2p(1−p) > 0 的概率被接受,所以期望轮数有限(等于 1 / (2p(1−p)))。面试时主动补一句:只有当 p 恰好是 0 或 1 时才会失败——那种硬币根本没有熵可提取。
rand5 → rand7:先扩位,再拒绝
本课的招牌套路。给你 rand5()——在 [0, 5) 上均匀,即 P(rand5() == 0) = 1/5——实现在 [0, 7) 上均匀的 rand7()。在 LeetCode 上你会遇到它的镜像版 LC 470 Implement Rand10() Using Rand7();技巧完全一样,在这里练熟一次即可。
想写 rand5() + rand5() 的直觉是个陷阱:和的范围是 0..8,但中间的值远比两端更容易出现(这是三角分布——凑出 0 只有一种方式,凑出 4 却有很多种)。正确做法是把两次调用当成 base-5 的两个数位,就像把坐标 hash 成一个数一样:
rand5()*5 + rand5() → [0, 25) 上均匀
rand5() (第二个数位,列)
0 1 2 3 4
+--------------------
0 | 0 1 2 3 4
r 1 | 5 6 7 8 9 25 个格子里的每一个
o 2 |10 11 12 13 14 都恰好被一个 (行, 列) 命中
w 3 |15 16 17 18 19 → 每个值概率 1/25
4 |20 21 22 23 24现在有了均匀的 rand25,但 25 不是 7 的整数倍。拒绝掉参差的尾巴:保留 0..20(这是 21 = 3 × 7 个等概率值),落在 21..24 就重摇。每个幸存值三个一组映射成一个 rand7 结果——tmp / 3(等价于 tmp % 7)。
public int rand7() {
int tmp = rand5() * 5 + rand5(); // [0, 25) 均匀
if (tmp < 21) return tmp / 3; // 保留 0..20 = 3*7,三个一组
return rand7(); // 拒绝 21..24 并重来
}
// 有些面试官更喜欢循环写法 —— 逻辑相同,不用递归
public int rand7Loop() {
int tmp;
do {
tmp = rand5() * 5 + rand5();
} while (tmp > 20);
return tmp / 3;
}推广到 randomM → randomN,由 m 和 n 相对大小的两个观察自然导出:
- m > n(如 rand25 → rand7):范围已经够大;拒绝到能放下的最大
n整数倍,再整除即可。 - m < n(如 rand5 → rand25):范围不够;把多次调用当数位组合——
randomM*M + randomM——把范围撑到盖过n,再照上面拒绝。 - m ≫ n(如 rand100 → rand9):成批分组——
⌊100/9⌋ = 11个值一桶,保留0..98、拒绝99,再除以 11。 - m ≪ n:无脑继续扩大(多拼几个数位)直到范围至少为
n。
永远不要把两次独立调用相加来扩大范围,也不要外加常数。和会在中间堆积;只有位置式组合(hi * base + lo)才能让联合分布保持平坦。如果你能讲清楚为什么相加是三角分布,就等于向面试官证明了你懂的是分布,而不是在背咒语。
rand2 → randN:一个 bit 拼出一切
把这个想法推到极限:只有 rand2()——一个公平 bit——为任意 N 构造 randN()。bit 是范围的原子:叠 k 个就能寻址 2^k 个值。可达范围按 2 的幂减一往上走:
k 个 bit 的最大值: 0 1 3 7 15 31 63 127 255 ... (2^k - 1)
表示 N 所需 bit 数: k = floor(log2(N)) + 1
10 bit → 1024 ≈ 1K
20 bit → 1024 * 1024 ≈ 100 万 (1M)
30 bit → 1024^3 ≈ 10 亿 (1G) 1 byte = 8 bit于是造 randN():取 k = ⌈log2 N⌉ 个 bit,用加权求和把它们拼成 [0, 2^k) 里的一个数(每来一个 bit,累加器翻倍),然后——又是那个熟悉的动作——拒绝所有 ≥ N 的值并重来。因为 2^k < 2N,接受概率超过一半,重试的成本很低。
// rand2() 返回 0 或 1,各 1/2
public int randN(int n) {
int bits = 1, range = 2;
while (range < n) { range *= 2; bits++; } // 最小的 2^bits >= n
while (true) {
int val = 0;
for (int i = 0; i < bits; i++)
val = val * 2 + rand2(); // 加权求和:拼出一个 k-bit 数
if (val < n) return val; // 接受
// 否则拒绝,重新摇所有 bit
}
}这就把整节课闭环了:rand2 → randN 是 rand5 → rand7 的原子版。无论手里是什么源——一个公平 bit、一个公平骰子、或一枚你已经去偏过的硬币——配方永远是那三个词:扩大、组合、拒绝。
Fisher–Yates:正确地洗一副牌
一道高频的偏 OOD 的题(类的建模那一半可以参考 Java 基础与设计题 那一课):设计一个 Deck 并实现 shuffle(),要求每张牌都等概率落在每个位置——一个均匀随机排列,每张牌在每个槽位都是 1/52。对应的 LeetCode 是 LC 384 Shuffle an Array。
算法是先随机、再交换,一个位置一个位置地走。固定位置 0,从全部 52 张牌里均匀选它的占位者;固定位置 1,从剩下的 51 张里选;以此类推。位置 0 拿到某张给定牌的概率是 1/52。位置 1 拿到某张给定牌的概率是 (51/52) · (1/51) = 1/52——51/52 是它在第 0 轮幸存的概率,1/51 是它此刻被选中的概率。这个连乘对每个槽位都成立,正好就是均匀性的证明。
class Deck {
private List<Card> cards;
private Random random = new Random();
// 正向:固定位置 i,从未洗的尾段 [i, n) 里抽它的占位者
public void shuffle() {
for (int i = 0; i < cards.size(); i++) {
int j = i + random.nextInt(cards.size() - i); // [i, n) 均匀
Collections.swap(cards, i, j);
}
}
// 反向:同样的保证,i 从 n-1 递减到 1,j 取 [0, i]
public void shuffleBackward() {
for (int i = cards.size() - 1; i >= 1; i--) {
int j = random.nextInt(i + 1); // [0, i] 均匀
Collections.swap(cards, i, j);
}
}
}面试官盯着找的 bug:在每一轮都从 [0, n) 均匀选 j,而不是从收缩的窗口 [i, n) 里选。那个版本会产生 n^n 条等概率执行路径映射到 n! 种排列,而 n^n 不能被 n! 整除,于是某些排列出现得更频繁——一种微妙但可证的非均匀。正确版和错误版之间只差这一行,而这一行就是整道题。两个正确变体都是 O(n) 时间、原地洗牌。
蓄水池抽样:采样一个存不下的数据流
笔记里的场景:安检口要从进场的人里等概率抽一个来检查,但人是无界地流进来的、你无法全部缓存——你必须在任意时刻都能回答「目前选中的是谁」,而每个人只经过你眼前一次。这就是蓄水池抽样(reservoir sampling),它支撑 LC 382 Linked List Random Node 和 LC 398 Random Pick Index。
单个抽取(k = 1):留下第一个到达者;当第 n 个人到达时,以 1/n 的概率替换当前选择。归纳很干净——假设 n − 1 个到达后每人概率是 1/(n−1);新人以 1/n 概率接管,任一在位者以 (1/(n−1)) · (n−1)/n = 1/n 幸存。所有人最终都落在 1/n。
// 从长度未知的数据流里等概率抽 1 个
int chosen = -1, count = 0;
for (int x : stream) {
count++; // x 是看到的第 n 个值
if (random.nextInt(count) == 0) // 概率 1/n
chosen = x;
}
// count==1 → 必被选中;后来者以 1/n 抢下槽位
// 抽 K 个(笔记里的 100 目标版本)
int[] reservoir = new int[100];
int n = 0;
for (int x : stream) {
if (n < 100) {
reservoir[n] = x; // 先用前 100 个填满池子
} else {
int j = random.nextInt(n + 1); // [0, n] 均匀
if (j < 100) reservoir[j] = x; // 以 100/(n+1) 进池
}
n++;
}全部魅力都在资源画像上:一遍扫描、O(k) 内存、无需知道流的长度。所以它是「从内存装不下的文件里抽样」或「在只能遍历一次的链表里随机取节点」的标准答案。当面试官强调流式或大小未知时,蓄水池抽样就是条件反射。
累积概率上的加权随机
不是所有分布都均匀。假设访客构成是 China 7、US 2、Japan 1,你要按这些权重成比例地抽一个国家。把权重首尾相接铺在数轴上,画面就是一排桶:
权重: China 7 US 2 Japan 1
|-----------|------|---|
0 7 9 10 ← 前缀和 = [7, 9, 10], total = 10
在 [0, 10) 里取均匀值 r:
r ∈ [0,7) → China r ∈ [7,9) → US r ∈ [9,10) → Japan前缀和就是累积分布。在 [0, total) 里取一个均匀值,再找第一个累积和超过它的桶——一个「第一个大于等于」的查找,也就是在前缀数组上做一次教科书式二分(正是第 1 课的二分模板)。这就是 LC 528 Random Pick with Weight。
class Solution {
private int[] prefix;
private int total;
private Random random = new Random();
public Solution(int[] w) {
prefix = new int[w.length];
int sum = 0;
for (int i = 0; i < w.length; i++) {
sum += w[i];
prefix[i] = sum; // 累积分布
}
total = sum;
}
public int pickIndex() {
int target = random.nextInt(total) + 1; // [1, total]
int left = 0, right = prefix.length - 1;
while (left < right) { // 第一个 prefix[i] >= target
int mid = left + (right - left) / 2;
if (prefix[mid] < target) left = mid + 1;
else right = mid;
}
return left;
}
}构造一次 O(n),每次抽取 O(log n)。同样这套机制也用于「在若干个带权矩形/区间里采样一个点」——先按权重挑区域,再在区域内均匀取点。还有笔记点到的一个回响:累积计数的想法跟 majority element / 数老板票数 的技巧是近亲——两者都是把一个总量在数轴上切成成比例的地盘。
随机数到底从哪来?
收尾题故意让人不安:不许调用任何随机函数,实现 random()。你无法从纯逻辑里凭空造熵,所以诚实的答案是点名一个外部来源——然后把上面的一切拿来塑形。
归约链是 random(n) → random(2) → getCurrentTime() % 2。高分辨率时钟的低位 bit(System.nanoTime() % 2)、线程调度的抖动、或一个硬件熵源,都能给你一个近似公平的 bit——一个 random(2)。把这个 bit 喂给前面的 rand2 → randN 构造器,你就有了任意范围的 random(n)。面试要考的不是 nanoTime() % 2 是个好 RNG(它又弱又可预测,任何安全敏感场景都不能用),而是整条层级最终坍缩成「一个公平 bit + 拒绝采样」。拿到一个 bit 的真熵,剩下的全是构造。
刷题清单
| 题目 | 套路 | 复杂度 |
|---|---|---|
| 有偏硬币 → 公平硬币 | von Neumann 拒绝(10/01) | 期望 O(1),1/(2p(1−p)) 轮 |
| rand5 → rand7 / LC 470 Rand10 from Rand7 | 扩位 + 拒绝尾巴 | 期望 O(1) |
| randomM → randomN | 组合数位 和/或 拒绝 | 期望 O(1) |
| rand2 → randN | k 个 bit + ≥ n 则拒绝 | 期望 O(log n) |
| LC 384 Shuffle an Array | Fisher–Yates 交换进 [i, n) | O(n),原地 |
| LC 382 / 398 蓄水池抽样 | 第 n 个到达者以 k/n 抢槽位 | O(n) 时间,O(k) 空间 |
| LC 528 Random Pick with Weight | 前缀和 + 二分 | O(n) 构造,O(log n) 抽取 |
| 无随机函数实现 random() | 时间/熵 bit → rand2 → randN | 每个值 O(log n) |
随机化是一个小工具箱,只有一个执念:证明它均匀。主干是 扩大 → 组合 → 拒绝——把弱源撑大,把多次调用当位置数位粘起来(绝不相加),再拒绝掉参差的余数让幸存者保持平坦。之上坐着三个有名字的套路:Fisher–Yates(交换进收缩的尾段)做排列、蓄水池抽样(第 n 个到达者以 k/n 抢槽)做数据流、前缀和 + 二分做加权选择。每次作答都把概率论证说出声——那才是面试官真正在打分的部分。
如何用有偏硬币造公平硬币? 抛两次;10 → 1、01 → 0,抛出 11/00 就丢弃重来。成立是因为 P(10) = P(01) = p(1−p) 精确相等,无论 p 是多少偏差都抵消。只有 p 为 0 或 1 时失败(von Neumann 技巧)。
如何用 rand5 造 rand7(或 Rand7 造 Rand10)? 当数位组合,不是相加:rand5*5 + rand5 是均匀的 [0,25)。保留 0..20(即 3×7),21..24 重摇,再 /3。把两次调用相加会得到三角分布——这就是陷阱。
什么是蓄水池抽样,何时用? 一遍扫描、O(k) 空间,从长度未知/极大的流里等概率抽 k 个。留下前 k 个;第 n 个到达者以 k/n 替换一个随机槽位,归纳可证均匀。支撑 LC 382 和 LC 398。
如何做加权随机选择? 对权重求前缀和(累积分布),在 [1, total] 取均匀值,二分找第一个 ≥ 它的桶。构造 O(n),抽取 O(log n)——LC 528。
正确的 Fisher–Yates 洗牌与经典 bug 是什么? i 从 [0, n) 走,把 i 和 [i, n) 里的随机 j 交换——收缩窗口是关键。每轮都从 [0, n) 里选会得到 n^n 条路径映射到 n! 种排列,可证有偏。