02.8.1.5 随机化与概率类
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.8 贪心与技巧题 / 02.8.1 贪心与技巧
02.8.1.5-001 随机化算法是什么?适用什么场景?
一句话结论
随机化算法在决策中引入随机数,以概率保证正确性或期望效率;适用于最坏情况难避免、平均表现良好、结果可概率接受的场景,如随机快排、随机哈希、抽样。
概念解释
- 随机决策:分支选择带概率。
- 概率保证:期望复杂度或以高概率正确。
- 对比确定性:不保证每次最坏最优。
原理流程
- 识别确定性最坏情况由输入顺序触发。
- 用随机打乱/随机选择消除顺序影响。
- 按概率口径分析复杂度。
代码 / 图示
随机快排:随机选基准;随机哈希:随机化哈希函数;抽样:随机选取
常见误区
- 误区:随机化能保证最优结果;正解:只给期望或概率保证,仍有小概率坏情况。
- 误区:随机化等于结果不可控;正解:概率分布可分析,工程上可接受。
追问
- Q:随机化算法分哪几类? A:蒙特卡洛(可能出错,重复降低错误率)与拉斯维加斯(结果必对,期望时间)。
- Q:面试怎么报复杂度? A:报期望复杂度,并说明最坏情况。
02.8.1.5-002 等概率随机与随机源要注意什么?
一句话结论
等概率指每个候选被选中概率相同;随机源给出的均匀区间需明确,映射到目标区间时避免取模偏差;面试题通常假设给定 nextInt(n) 已均匀返回 [0,n)。
概念解释
- 均匀:每个取值等概率。
- 区间映射:源范围到目标范围。
- 偏差:取模尾段不均。
原理流程
- 确认随机源范围与均匀性。
- 映射到目标区间。
- 必要时拒绝采样修正偏差。
代码 / 示例
int pick = rand.nextInt(n); // [0, n) 均匀
常见误区
- 误区:
rand() % n永远均匀;正解:源范围不被 n 整除时有偏差。 - 误区:随机源可重复使用不影响分布;正解:状态推进方式影响后续序列。
追问
- Q:随机种子作用? A:固定种子复现序列,调试用。
- Q:密码学随机与普通随机区别? A:前者不可预测,普通伪随机可被预测。
02.8.1.5-003 Fisher-Yates 洗牌算法怎么做?
一句话结论
从后往前(或从前往后)遍历,当前位置与 [0,i](或 [i,n))随机位置交换;每轮把随机候选放入当前位,保证每个排列等概率;时间 O(n),原地。
概念解释
- 原地交换:不额外开结果数组。
- 候选区间:未固定位置。
- 等概率:每步随机选择贡献均匀分布。
原理流程
- i 从 n-1 到 1。
- j = rand(0, i)。
- 交换 a[i] 与 a[j]。
代码 / 示例
void shuffle(int[] a) {
Random r = new Random();
for (int i = a.length - 1; i > 0; i--) {
int j = r.nextInt(i + 1);
int t = a[i]; a[i] = a[j]; a[j] = t;
}
}
常见误区
- 误区:每位置与全数组随机位置交换;正解:候选区间限定未固定部分,否则分布不均。
- 误区:从前往后交换时候选写成 [0,n);正解:对应方向候选区间要匹配。
追问
- Q:复杂度? A:O(n) 时间,O(1) 额外空间。
- Q:为什么不能用排序加随机键? A:随机键排序分布受键重复与排序稳定性影响,不等价均匀洗牌。
02.8.1.5-004 怎么证明洗牌后每个排列等概率?
一句话结论
归纳证明:第 i 轮把某元素放入位置 i 的概率为 1/(i+1);逐步相乘,任一排列被构造概率为 1/n!;每步选择独立贡献均匀性。
概念解释
- 排列数:n!。
- 逐步概率:每位置选择概率相乘。
- 归纳:前缀固定后剩余均匀。
原理流程
- 基准:单元素排列概率 1。
- 归纳步:当前位 1/(i+1) 概率选中目标元素。
- 乘积得 1/n!。
代码 / 图示
P(排列) = 1/n × 1/(n-1) × ... × 1/1 = 1/n!
常见误区
- 误区:只证明元素位置随机;正解:要证明整体排列分布均匀。
- 误区:交换两次就抵消偏差;正解:偏差来自候选区间,需算法结构保证。
追问
- Q:从前往后版本概率怎么推? A:对称,候选 [i,n),同样归纳得均匀。
- Q:等概率与元素重复有关吗? A:重复元素下不同排列不可区分,概率口径按可见结果计。
02.8.1.5-005 蓄水池抽样怎么从未知长度数据流抽 k 个?
一句话结论
前 k 个元素先入蓄水池;第 i 个元素(i > k)以 k/i 概率被选中,随机替换池中一个位置;遍历结束后池中 k 个元素等概率被抽中,无需知道总长度。
概念解释
- 蓄水池:容量 k 的结果集。
- 进入概率:第 i 个以 k/i 入选。
- 替换:等概率替换池中位置。
原理流程
- 前 k 个入池。
- 第 i 个生成 [0,i) 随机数,< k 则替换对应池位。
- 流结束输出池。
代码 / 示例
// for i = k..n-1:
// int j = rand.nextInt(i + 1);
// if (j < k) reservoir[j] = data[i];
常见误区
- 误区:先读完流存数组再随机抽;正解:蓄水池面向无法保存全量的数据流。
- 误区:替换概率写成 1/i;正解:入选概率 k/i,替换池内位置等概率。
追问
- Q:k=1 时概率? A:每个元素 1/i 替换,最终等概率抽一个。
- Q:复杂度? A:O(n) 时间,O(k) 空间。
02.8.1.5-006 蓄水池抽样的等概率怎么证明?
一句话结论
归纳证明第 i 个元素最终留在池中的概率为 k/n:入选概率 k/i,之后每次被保留概率为 1 - 1/j(j > i),连乘化简得 k/n;与位置无关即等概率。
概念解释
- 入选:k/i。
- 保留:后续轮次未被替换。
- 连乘: telescoping 化简。
原理流程
- 写出元素 i 入选概率。
- 乘后续各轮保留概率。
- 化简得 k/n。
代码 / 图示
P(i 留池) = k/i × ∏_{j=i+1}^{n}(1 - 1/j) = k/n
常见误区
- 误区:只证明入选概率;正解:还要算后续被替换后的保留概率。
- 误区:池内元素地位不同;正解:对称替换保证池内等权。
追问
- Q:加权蓄水池了解吗? A:按权重生成随机键,保留键最大的 k 个。
- Q:流长度已知还需要蓄水池吗? A:可直接随机索引抽取,蓄水池用于未知/流式。
02.8.1.5-007 加权随机抽样怎么做?
一句话结论
元素带权重,按权重比例被抽中;先求权重前缀和,生成 [0, 总权重) 随机数,二分找首个前缀和大于随机数的元素;权重即概率比例。
概念解释
- 权重:相对选中概率。
- 前缀和:累积权重区间。
- 二分定位:随机落点对应元素。
原理流程
- 计算前缀和数组。
- 随机数落在总权重内。
- 二分找区间归属。
代码 / 示例
// prefix[i] = 前 i 个权重和;x = rand(prefix[n]); 二分 upper_bound(x)
常见误区
- 误区:权重归一化成概率再取;正解:直接用权重前缀和,避免浮点误差。
- 误区:线性扫描定位;正解:二分 O(log n),前缀和已排序。
追问
- Q:权重为 0 怎么办? A:该元素区间为空,不会被选中。
- Q:复杂度? A:建表 O(n),每次抽样 O(log n)。
02.8.1.5-008 前缀和 + 二分在加权抽样中怎么落地?
一句话结论
前缀和严格递增(权重非负);随机数 r ∈ [0, total),二分找最小 i 使 prefix[i] > r;该 i 即抽中元素;重复抽样每次独立生成 r。
概念解释
- 区间归属:prefix[i-1] <= r < prefix[i]。
- 二分:找上界位置。
- 独立抽样:每次重新随机。
原理流程
- 建前缀和。
- 生成 r。
- 二分定位并返回索引。
代码 / 示例
int pick(int[] prefix, int total) {
int r = rand.nextInt(total);
int lo = 0, hi = prefix.length - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (prefix[mid] <= r) lo = mid + 1; else hi = mid;
}
return lo;
}
常见误区
- 误区:前缀和含零权重导致相等值;正解:上界二分仍可定位,但需确认口径。
- 误区:随机数取到 total;正解:区间左闭右开 [0, total)。
追问
- Q:关联二分页面? A:边界二分见 02.5.1.1。
- Q:权重动态更新怎么办? A:需可更新的前缀结构(树状数组/线段树)。
02.8.1.5-009 打乱数组(LC 384)怎么设计?
一句话结论
保存原始数组,reset 返回副本,shuffle 对副本做 Fisher-Yates 原地洗牌;保证原始数据不被破坏,洗牌结果均匀。
概念解释
- 原始副本:reset 数据源。
- 洗牌副本:每次打乱独立。
- 均匀性:Yates 算法保证。
原理流程
- 构造存原数组。
- reset 复制返回。
- shuffle 复制后原地交换。
代码 / 示例
class Solution {
int[] orig;
public Solution(int[] nums) { orig = nums.clone(); }
public int[] reset() { return orig.clone(); }
public int[] shuffle() {
int[] a = orig.clone();
// Fisher-Yates 交换
return a;
}
}
常见误区
- 误区:shuffle 直接改原数组;正解:先克隆再洗,否则 reset 无法还原。
- 误区:每次 shuffle 基于上次结果继续洗;正解:应从原始副本重新克隆。
追问
- Q:reset 返回引用还是副本? A:返回副本,防止外部修改内部原始数据。
- Q:复杂度? A:reset O(n),shuffle O(n)。
02.8.1.5-010 伪随机数生成器了解哪些概念?
一句话结论
伪随机数由确定性算法(如线性同余)从种子产出周期序列,分布近似均匀但可预测;工程面试掌握种子、周期、均匀性概念即可,不要求实现算法。
概念解释
- 种子:序列起点。
- 周期:序列重复长度。
- 伪随机:确定性产出,非真随机。
原理流程
- 种子初始化状态。
- 迭代生成下一随机值。
- 映射到目标区间。
代码 / 图示
seed → 状态迭代 → 随机序列 → 区间映射
常见误区
- 误区:伪随机不可复现;正解:同种子同序列,可复现。
- 误区:伪随机适合安全场景;正解:可预测,安全场景用密码学随机源。
追问
- Q:线性同余公式? A:x_{n+1} = (a·x_n + c) mod m,了解即可。
- Q:随机源不足够均匀怎么办? A:先做区间映射校验,必要时换源。
02.8.1.5-011 抛硬币/骰子类期望怎么算?
一句话结论
期望 = 各结果值 × 概率之和;独立试验期望可线性相加;先列结果与概率,再按定义计算;几何分布(首次成功)期望有闭式结论。
概念解释
- 期望:概率加权平均。
- 独立性:联合概率相乘。
- 线性性:期望可加,不要求独立。
原理流程
- 列可能结果与概率。
- 值乘概率累加。
- 多轮试验用线性性合并。
代码 / 示例
E = Σ x_i · p_i;抛硬币正面期望次数(几何分布)= 1/p
常见误区
- 误区:期望取最可能结果;正解:是加权平均,不一定是可行结果。
- 误区:多轮期望相乘;正解:期望相加,概率相乘区分清楚。
追问
- Q:与概率 DP 关系? A:期望转移按分支概率加权,见 02.7.2.4。
- Q:方差需要算吗? A:面试一般只问期望。
02.8.1.5-012 蒙特卡洛方法是什么思想?
一句话结论
通过大量随机采样近似求解难以解析计算的问题(面积、概率、最优值);采样越多近似越准;核心是用随机试验替代精确公式,结果带统计误差。
概念解释
- 采样:随机生成样本。
- 近似:频率估计概率/面积。
- 误差:样本量增大收敛。
原理流程
- 定义采样空间与判定规则。
- 大量随机采样统计命中比例。
- 比例乘以总量得估计值。
代码 / 图示
投点 → 命中计数 → 频率 × 区域总量 ≈ 目标值
常见误区
- 误区:蒙特卡洛给精确答案;正解:是近似估计,有置信区间。
- 误区:少量样本就下结论;正解:需足够样本量收敛。
追问
- Q:蒙特卡洛与拉斯维加斯区别? A:前者结果可能近似/出错,后者结果必对、时间随机。
- Q:复杂度口径? A:按采样次数评估,与精度要求相关。
02.8.1.5-013 随机化快速排序为什么能避免最坏情况?
一句话结论
普通快排最坏由有序输入触发固定坏基准;随机选基准使划分失衡概率低,期望 O(n log n);最坏 O(n²) 仍存在但概率极低。
概念解释
- 基准:划分支点。
- 失衡:一侧极长导致递归退化。
- 随机化:消除输入顺序对基准质量的影响。
原理流程
- 随机选一个元素交换到基准位。
- 划分左右。
- 递归两侧。
代码 / 示例
// pivot = rand 区间内随机下标,交换到端点后划分
常见误区
- 误区:随机快排保证 O(n log n);正解:是期望 O(n log n),最坏仍 O(n²)。
- 误区:随机化后无需关注重复元素;正解:重复多需三路划分,见 02.5.2.2。
追问
- Q:期望复杂度怎么推? A:基准排名均匀分布,递归期望深度对数。
- Q:关联排序页面? A:快排与三路划分见 02.5.2.2。
02.8.1.5-014 随机化在哈希表中起什么作用?
一句话结论
哈希函数随机化(随机种子/随机乘法因子)使恶意构造的碰撞输入分布均匀,避免退化为链表查找;工程哈希表用随机扰动抵御最坏输入。
概念解释
- 碰撞:多键映射同桶。
- 随机映射:键到桶位分布近似均匀。
- 抗退化:避免全部落同桶。
原理流程
- 哈希函数引入随机因子。
- 键均匀散列到桶。
- 冲突按链表/开放寻址处理。
代码 / 图示
hash = 随机化函数(key) mod 桶数
常见误区
- 误区:哈希随机化能消除所有冲突;正解:只均匀分布,冲突仍可能发生。
- 误区:随机因子每次查询都变;正解:同一表内因子固定。
追问
- Q:哈希冲突处理见哪页? A:02.2.2.1 哈希表设计与冲突处理。
- Q:负载因子影响什么? A:扩容阈值,关系平均查找长度。
02.8.1.5-015 随机抽取链表节点怎么做?
一句话结论
长度未知的链表抽一个节点:遍历中第 i 个节点以 1/i 概率替换当前结果;等价 k=1 蓄水池抽样;一次遍历完成,无需先求长度。
概念解释
- 单元素蓄水池:结果指针。
- 替换概率:1/i。
- 流式:不存储全部节点。
原理流程
- 结果指向首节点。
- 第 i 个节点以 1/i 概率替换结果。
- 遍历结束返回结果。
代码 / 示例
// i = 1; for (node : list) { if (rand.nextInt(i) == 0) ans = node; i++; }
常见误区
- 误区:先遍历数长度再随机索引;正解:蓄水池一次遍历,空间 O(1)。
- 误区:替换概率写成 1/n;正解:流式未知 n,按当前序号 i 概率。
追问
- Q:抽 k 个节点? A:k=蓄水池容量,同 02.8.1.5-005。
- Q:复杂度? A:O(n) 时间,O(1) 空间。
02.8.1.5-016 拒绝采样怎么用?
一句话结论
目标分布复杂时,从易采样的提议分布生成样本,按接受概率保留/拒绝;接受率足够高时近似目标分布;LC 470 类用 rand7 生成 rand10 即拒绝越界样本。
概念解释
- 提议分布:易生成。
- 接受规则:按概率保留。
- 拒绝:丢弃不接受样本重采。
原理流程
- 提议采样。
- 按规则判断接受。
- 拒绝则重新采样。
代码 / 示例
rand7 → 两轮组合得 1~49;保留 1~40,映射 1~10,41~49 拒绝重采
常见误区
- 误区:直接取模压缩区间;正解:边界不整除会有偏差,拒绝采样保证均匀。
- 误区:拒绝次数无上限;正解:期望采样次数可算,接受率决定效率。
追问
- Q:rand7 生成 rand10 接受率? A:40/49。
- Q:复杂度? A:期望 O(1),拒绝轮次几何分布。
02.8.1.5-017 概率 DP 与随机算法是什么关系?
一句话结论
概率 DP 在确定状态转移下按概率加权求期望/概率结果;随机算法主动引入随机决策获得期望效率;前者求分布量,后者用随机优化复杂度,思路不同但都以概率分析为工具。
概念解释
- 概率 DP:状态 + 概率转移。
- 随机算法:决策带随机。
- 概率分析:期望/分布口径。
原理流程
- 判断问题是求概率/期望还是优化效率。
- 概率结果 → DP 转移加权。
- 效率问题 → 随机化选择。
代码 / 图示
概率 DP:E[cur] = Σ p·(cost + E[next]);随机算法:随机选基准/候选
常见误区
- 误区:概率题都用随机模拟;正解:能列转移方程时 DP 更精确。
- 误区:随机化算法结果用 DP 求;正解:二者目标不同。
追问
- Q:概率 DP 见哪页? A:02.7.2.4 数位 DP 与其他。
- Q:期望线性性在两者都用吗? A:是,期望可分项累加。
02.8.1.5-018 期望线性性怎么用?
一句话结论
E[X+Y] = E[X]+E[Y],不要求 X、Y 独立;复杂期望可拆成指示变量之和分别求期望再相加,是概率题最常用的化简手段。
概念解释
- 指示变量:事件发生为 1,否则 0。
- 线性性:期望可加。
- 拆分:把总量拆成若干 0/1 贡献。
原理流程
- 把目标量拆为分项之和。
- 求每项期望(概率)。
- 累加得总期望。
代码 / 示例
E[总次数] = Σ E[指示变量] = Σ P(事件发生)
常见误区
- 误区:期望可加需要独立;正解:线性性不要求独立。
- 误区:把概率相乘当期望;正解:和用加,积才用乘。
追问
- Q:关联 DP 期望转移? A:每步代价期望加权累加,见 02.7.2.4。
- Q:指示变量难定义怎么办? A:按“是否贡献一次”逐项拆分。
02.8.1.5-019 随机算法怎么保证可复现与可测试?
一句话结论
固定随机种子即可复现序列;测试时分别验证确定性逻辑与概率口径(边界、区间、替换规则);不把随机输出当作断言唯一依据,概率性质用多轮统计或数学证明核对。
概念解释
- 种子固定:序列可重现。
- 逻辑测试:非随机部分单测。
- 概率验证:大样本频率近似理论概率。
原理流程
- 注入随机源便于替换种子。
- 固定种子跑确定性用例。
- 大样本统计核对分布。
代码 / 示例
Random r = new Random(seed); // 固定种子复现
常见误区
- 误区:测试断言洗牌后某具体顺序;正解:顺序随机,断言合法性与均匀口径。
- 误区:生产用固定种子;正解:生产随机,仅调试/测试固定。
追问
- Q:随机源怎么注入? A:构造函数传入 Random,便于测试替换。
- Q:概率测试样本量? A:足够大使频率接近理论值,注意波动。
02.8.1.5-020 概率/随机类题常见误区有哪些?
一句话结论
误区集中在:取模偏差未修正、概率与期望混淆、独立与不独立混用、洗牌候选区间错误、抽样概率写错、把近似当精确;复盘按“分布口径 → 概率公式 → 算法结构”逐项核对。
概念解释
- 分布:等概率/加权。
- 公式:概率相乘、期望相加。
- 结构:候选区间、替换规则。
原理流程
- 核对随机映射是否均匀。
- 区分概率、期望、计数。
- 复查抽样/洗牌规则结构。
代码 / 图示
均匀性 → 概率公式 → 候选区间/替换概率 → 复现与测试
常见误区
- 误区:加权抽样按等概率抽;正解:前缀和按权重区间定位。
- 误区:蓄水池替换概率写反;正解:入选 k/i,池内等概率替换。
追问
- Q:概率题面试先讲什么? A:结果空间、概率口径,再给算法。
- Q:不确定概率结论怎么办? A:标注待确认,列出需验证的采样/公式点。