LeetCode 1227. 飞机座位分配概率
题目描述
题意分析
n位乘客依次登机，座位也按乘客编号对应。第一位丢失座位信息，从所有座位中等概率选一个；后续乘客若自己的座位空着就坐自己的，否则从剩余空座中等概率选择。求最后一位乘客最终坐到自己座位的概率。这里关注的是指定座位是否保留到最后，不是最后一个人是否还能找到空座；人数与座位数相同，他总有一个座位可以坐。
解法：概率对称结论
核心思路
[!blue]
把座位
1和座位n作为两个特殊位置。只要被迫随机选座的人选中了座位1，错位传递就结束：当前乘客占据最初空出的座位1，不再挤占未登机者的位置，后续尚未登机者的座位都没有被额外占用，最后一位可以坐到自己的座位。如果在这之前有人随机选中了座位
n，最后一位的座位已经被占，最终必然失败。如果随机选中其他尚未登机者的座位，只会让对应乘客稍后成为下一个被迫随机选座的人，结果还未确定。在胜负尚未确定时，座位
1与座位n一直都空着：前者一旦被选就已经成功，后者一旦被选就已经失败。每次随机选择都在所有空座中等概率进行，这两个特殊座位的被选概率完全相同，其余选择只是把过程继续传给后面的乘客。因此，任何尚未结束的过程都对这两个结局保持对称。随机传递最终一定会碰到其中一个特殊座位，于是“先选座位
1”与“先选座位n”的总概率相等，二者合计为1，成功概率就是1/2。当
n = 1时，这两个特殊位置重合，唯一乘客必然坐到唯一座位，不能再套用两个不同结局的对称性，答案为1。
解题步骤
- 若只有一位乘客，返回
1.0。- 否则首位与末位座位不同，根据先被随机选中的对称性，返回
0.5。
代码实现
class Solution {
public double nthPersonGetsNthSeat(int n) {
// 只有一个座位时两个特殊座位重合，成功概率为一。
if (n == 1) {
return 1.0;
}
// 结果确定前，一号与最后一号始终是对称的空座选择。
return 0.5;
}
}
func nthPersonGetsNthSeat(n int) float64 {
// 只有一个座位时两个特殊座位重合，成功概率为一。
if n == 1 {
return 1.0
}
// 结果确定前，一号与最后一号始终是对称的空座选择。
return 0.5
}
复杂度分析
- 时间复杂度：$O(1)$。
- 空间复杂度：$O(1)$。
关键点总结
[!green]
- 中间座位只负责传递谁来随机选座，不直接决定最终是否成功。
- 结果未确定前，两张特殊座位同时为空、每次被选择概率相等，这是对称性成立的依据。
- 两种结局终将发生一个，结合对称性才能推出各占一半。
易错点总结
[!yellow]
- 只计算第一位直接选中自己座位的概率，会漏掉后续错位传递中恢复秩序的情况。
- 认为乘客人数变化会破坏结论，忽略了两个特殊空座在每一步仍保持对称。
- 不单独处理
n = 1，会把唯一座位这个必然事件错误算成一半。- 使用整数表达式
1 / 2，会在整数除法中得到零，应直接返回浮点数0.5。
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！