LeetCode 1227. 飞机座位分配概率

2024-11-26 HGNULB 约 10 分钟

文章信息 8 个分类 4 个标签

分类

题目描述

✅ 1227. 飞机座位分配概率

题意分析

有 n 位乘客和 n 个座位，票号与座位号一一对应。第 1 位乘客把票弄丢了，在 n 个座位里等概率随机挑一个坐下。之后的每一位乘客上机时，如果自己票上的座位还空着就坐自己的；如果被别人占了，就在当前所有空座里等概率随机挑一个坐下。问第 n 位乘客最终坐到第 n 号座位的概率是多少。

先把随机过程的传染链条看清楚：只有当某位乘客发现自己的座位被占时，才会产生新的随机选择。而第 1 位乘客选了座位 k 之后，票号 2 到 k-1 的乘客座位都好好空着，他们会安安静静坐下、不引入任何随机性；真正被"传染"的是乘客 k，随机性从第 1 位手里交接到了他手里。

这条链条有两个吸收态：一旦有人坐到座位 1，后面所有乘客（包括第 n 位）的座位都不会再被占，随机性彻底终止，第 n 位必定坐到自己的位置；一旦有人坐到座位 n，第 n 位就已经出局，无论后面怎么走都没救了。除这两个座位外，选中任何中间座位都只是把随机性往后推一棒，不产生结论。

约束里 n 最大到 10^5，而返回值是浮点数且允许 10^-5 的误差。这两条合起来说明：既不可能模拟随机过程（模拟只能得到近似频率，精度不可控且不可复现），也不该期待一个需要遍历 n 的复杂表达式——数据范围这么大却只要一个数，通常意味着答案有闭式形式。

边界只有一个：n = 1 时第 1 位乘客就是第 n 位乘客，他随机选座但只有一个座位可选，必然坐到自己的位置，答案是 1。这一档必须单独回答，因为它不满足下面推导所依赖的"座位 1 和座位 n 是两个不同的座位"这个前提。

解法：概率对称结论

核心思路

最直接的想法是模拟：跑几百万次随机实验，统计第 n 位乘客坐到自己座位的频率。这条路的瓶颈很硬——它给不出精确值，误差随试验次数只以 $O(1/\sqrt{m})$ 的速度收敛，要稳定压到 10^-5 需要天文数字级别的次数，而且结果不可复现。所以必须转向精确推导。

于是定义状态：f(n) 表示在「有 n 位乘客、n 个座位，且第 1 位乘客丢票随机选座」这个局面下，最后一位乘客坐到自己座位的概率。

按第 1 位乘客选中的座位 k 分类讨论，每种情况的概率都是 1/n：选中 k = 1，之后人人对号入座，最后一位必然成功，贡献 1；选中 k = n，最后一位的座位当场被占，贡献 0；选中中间的某个 k（2 ≤ k ≤ n-1），乘客 2 到 k-1 全部对号入座并退出局面，轮到乘客 k 时他发现座位被占，于是在剩下的 n-k+1 个空座里随机选一个——注意此刻剩下的空座恰好是 {座位 1} ∪ {座位 k+1 … 座位 n}，而乘客也恰好是 k, k+1, …, n 这 n-k+1 位，其中只有乘客 k 的座位缺席。把座位 1 在新局面里重新扮演「丢票者本该坐的位置」的角色，这就和原问题一模一样，规模变成 n-k+1。

于是得到递推 f(n) = 1/n · 1 + 1/n · 0 + (1/n) · Σ_{k=2}^{n-1} f(n-k+1)，其中求和项即 f(n-1) + f(n-2) + … + f(2)。

手算前几项：f(1) = 1；f(2) = 1/2 · 1 + 1/2 · 0 = 1/2（求和项为空）；f(3) = 1/3 · 1 + 1/3 · 0 + 1/3 · f(2) = 1/3 + 1/6 = 1/2；f(4) = 1/4 + 1/4 · (f(3) + f(2)) = 1/4 + 1/4 · 1 = 1/2。归纳假设 f(2) = … = f(n-1) = 1/2，则 f(n) = 1/n + (1/n) · (n-2) · (1/2) = 1/n + (n-2)/(2n) = (2 + n - 2)/(2n) = 1/2，归纳成立。所以 n ≥ 2 时答案恒为 1/2。

递推之外还有一个一句话就能说清的对称论证，面试里更好用：整个随机过程一定会在第一次有人坐到座位 1 或座位 n 的那一刻决出胜负——中间座位只负责传棒，不决定结果。而在每一次随机选择中，当前的选择者面对的空座集合必然同时包含座位 1 和座位 n（座位 1 未被占是因为它一旦被占过程就结束了，座位 n 同理），且这两个座位被选中的概率完全相等。两个地位对称的吸收态被先选中的机会各占一半，所以答案是 1/2。

这个结论意味着代码里根本不需要任何循环或数组：只要把 n = 1 单独挑出来，其余一律返回 0.5。

解题步骤

判断 n == 1 并直接返回 1.0。为什么要单列：n = 1 时座位 1 和座位 n 是同一个座位，两个吸收态重合，对称论证的前提不成立；从过程看，第 1 位乘客在唯一的空座里"随机"选，必然选中自己的座位，概率是 1 而不是 1/2。

其余情况返回 0.5。为什么不需要按 n 的奇偶或大小再分档：上面的归纳已经证明 f(2) = f(3) = f(4) = … = 1/2，这是一个与 n 完全无关的常数，n = 2 和 n = 10^5 的答案没有任何区别。

返回值用浮点类型。为什么：概率不是整数，Java 里方法签名要求 double，Go 里是 float64；写成整数除法会让 1/2 变成 0。代码里直接写字面量 1.0 和 0.5，避开除法本身就绕开了这个坑。

以 n = 3 手工枚举验证一遍（第 1 位乘客等概率选三个座位之一，各 1/3）：

第 1 位选座位 1（概率 1/3）：第 2 位的座位 2 空着，坐自己的；第 3 位的座位 3 空着，坐自己的。成功，这一支贡献 1/3 × 1 = 1/3。

第 1 位选座位 2（概率 1/3）：第 2 位发现座位 2 被占，在空座 {1, 3} 中各以 1/2 概率选。选座位 1（1/2）则第 3 位的座位空着，成功；选座位 3（1/2）则第 3 位无座，失败。这一支贡献 1/3 × 1/2 = 1/6。

第 1 位选座位 3（概率 1/3）：第 3 位的座位当场被占，第 2 位正常坐自己的座位，失败，贡献 0。

汇总：1/3 + 1/6 + 0 = 1/2，与 f(3) = 0.5 一致。

顺带看清对称性在这个例子里是怎么体现的：第二支里，随机性交到第 2 位手上时，他面对的空座恰好是 {座位 1, 座位 3}——正是两个吸收态，各占一半。整个过程无论 n 多大，最后一步永远是这样一个二选一。

代码实现

class Solution {
    public double nthPersonGetsNthSeat(int n) {
        // n = 1 时座位 1 与座位 n 重合，两个吸收态合并，概率为 1。
        if (n == 1) {
            return 1.0;
        }
        // n >= 2 时座位 1 与座位 n 地位对称，先被选中的机会各占一半。
        return 0.5;
    }
}

func nthPersonGetsNthSeat(n int) float64 {
    // n = 1 时座位 1 与座位 n 重合，两个吸收态合并，概率为 1。
    if n == 1 {
        return 1.0
    }
    // n >= 2 时座位 1 与座位 n 地位对称，先被选中的机会各占一半。
    return 0.5
}

复杂度分析

时间复杂度：$O(1)$。凭什么：函数体只有一次整数比较和一次返回，不含任何循环或递归，执行时间与 n 的大小完全无关，n = 10^5 和 n = 2 跑得一样快。

空间复杂度：$O(1)$。凭什么：没有申请数组、没有递推表、没有递归栈，只有入参和返回值占用固定的栈空间。即便按上面的递推式写成 dp，也只需要维护一个前缀和而不是整张表，但结论化之后连这个都省了。

关键点总结

遇到"随机过程 + 求概率 + 数据范围很大"的组合，先别急着模拟，而是问一句：这个过程有没有吸收态？ 找出让结果就此确定的那几个事件，往往就能把无穷多条随机路径压缩成几个等概率的分支。

递归化简的关键动作是识别子问题的同构。本题中"乘客 k 发现座位被占、面对 n-k+1 个空座"这个局面，和原始的"丢票乘客面对 n 个空座"在结构上完全一致，只是把座位 k 的角色换成了座位 1。看不出这层同构，递推式就写不出来。

先用递推手算前几项再猜结论、最后用归纳法回证，是数学结论题的标准打法。f(2) = f(3) = f(4) = 1/2 三项一致就足以让人怀疑答案是常数，验证成本远低于硬推。

对称性论证比递推更短也更漂亮，但它的适用前提要说清楚：必须证明每次随机选择时两个吸收态都还在候选集合里且概率相同。本题里这一点恰好成立，n = 1 则因为两个吸收态重合而失效——例外恰恰暴露了论证依赖什么。

面试视角：这题的正确打开方式是先说思路再写代码。只甩一句"答案就是 0.5"会被认为是背过题，面试官真正想听的是"为什么只有座位 1 和座位 n 重要"和"为什么它们对称"。稳妥的做法是先讲对称性直觉，再补一句"我也可以写出递推式并用归纳法证明"，最后才写那三行代码。

常数级答案不代表可以跳过边界检查。n = 1 这个唯一的例外正好是最容易被跳过的那档，写完结论式代码后主动回头验证最小输入，是这类题的必备动作。

易错点总结

直接返回 0.5 不判 n == 1：输入 n = 1 时应输出 1.00000，实际输出 0.50000，第一个测试用例就挂。

误以为 n = 2 也是特殊情况而返回 1.0：n = 2 时第 1 位在两个座位中各以 1/2 概率选，正确答案就是 0.5，这样写会在第二个用例上出错。

想当然认为概率随 n 增大而趋近某个值，写成 1.0 / n 或 (n - 1.0) / n：n = 3 时分别输出 0.33333 和 0.66667，都与正确的 0.5 不符——概率与 n 无关这件事反直觉，但确实如此。

用整数除法写 return 1 / 2;：Java 里 1 / 2 是整型除法结果为 0，隐式转成 double 后返回 0.0；Go 里 1 / 2 同样是无类型整数常量运算，得到 0。所有 n ≥ 2 的用例全错。

老老实实模拟随机过程并统计频率：n = 10^5 时单次模拟就要 O(n)，为了把误差压到 10^-5 需要跑上亿次实验，必然超时；即使勉强跑完，结果也会在 0.5 附近抖动，同一份代码提交两次可能一次过一次不过。

按递推式老实开数组做 dp 而不化简：写成 f[i] = (1 + Σ_{j=2}^{i-1} f[j]) / i 的双重循环是 $O(n^2)$，n = 10^5 时约 10^10 次运算，必然超时；即使用前缀和优化到 $O(n)$ 也是在算一串全等于 0.5 的数，纯属浪费。

递推里把中间座位的求和范围写成 k 从 2 到 n：多算进了 k = n 这一支，而它本该贡献 0 却被当成 f(1) = 1 计入，手算 f(3) 会得到 2/3 而不是 1/2，推导从这里就跑偏了。

认为只要座位 1 被占最后一位就完蛋：搞反了两个吸收态的方向。座位 1 被占意味着过程终止且后续人人对号入座，是成功信号；只有座位 n 被占才是失败。方向弄反会推出答案恒为 0。

在讲解里说"因为第一个乘客有 1/n 的概率坐对，所以答案是 1/n"：这只算了第一步，忽略了随机性会往后传递并在中间座位上继续演化，n = 3 时会给出 1/3 而非 1/2。

相似题目

题目	难度	考察点
292. Nim 游戏	简单	同样是"手算前几项 → 猜结论 → 归纳回证"，最终压缩成一行取模判断
319. 灯泡开关	中等	从模拟中提炼出"约数个数为奇数当且仅当是完全平方数"，答案化为一次开方
390. 消除游戏	中等	同构子问题的规模递归，需要在每轮反向操作中重新映射首元素
688. 骑士在棋盘上的概率	中等	概率无法化成闭式，必须老实用 dp 逐步转移，正好是本题的反面对照
877. 石子游戏	中等	结论同样是常数（先手必胜），但需要用奇偶染色而非概率对称来论证
470. 用 Rand7() 实现 Rand10()	中等	反过来构造等概率分布，靠拒绝采样保证均匀性并分析期望调用次数
528. 按权重随机选择	中等	把给定的离散概率分布转成前缀和加二分，考察随机采样的工程实现