飞机座位分配概率Java
文章发布较早，内容可能过时，阅读注意甄别。
# 题目
有 n 位乘客即将登机，飞机正好有 n 个座位。第一位乘客的票丢了，他随便选了一个座位坐下。
剩下的乘客将会：
如果他们自己的座位还空着，就坐到自己的座位上，
当他们自己的座位被占用时，随机选择其他座位
第 n 位乘客坐在自己的座位上的概率是多少？
示例 1：
输入：n = 1
输出：1.00000
解释：第一个人只会坐在自己的位置上。
示例 2：
输入: n = 2
输出: 0.50000
解释：在第一个人选好座位坐下后，第二个人坐在自己的座位上的概率是 0.5。
提示：
- 1 <= n <= 10^5
# 思路
因为我们不知道乘客对应哪个座位
# 解法
class Solution {
public double nthPersonGetsNthSeat(int n) {
/*
因为我们不知道乘客对应哪个座位
因此我们直接按入场顺序给它们的座位编号
1 号乘客是 1 号座位，(ps：1 号 票丢了，并不知道自己坐 1 号座位)
2 号乘客 是 2 号座位
。。。
我们要求的是最后一位乘客 n 最终能坐到自己座位，即 n 号座位的概率
因为 1 号 票丢了，因此分析 1 号 坐不同座位的情况，它有 3 种选择
1、1 号有 1 / n 的概率 坐到 1 号座位，那么不会对 [2, n] 号乘客产生影响，因为它们都有票，那么 n 号乘客坐到自己座位的概率为 1
2、1 号有 1 / n 的概率 坐到 n 号座位，那么 n 号 肯定坐不到 n 号座位，那么概率为 0
3、1 号有 n - 2 / n 的概率 坐到 [2, n - 1] 号座位，假设是 k 号座位，
那么对于 k 号乘客来说它有 3 种选择
1、k 号有 1 / n - 1 的概率 坐到 1 号座位，那么不会对其他乘客产生影响，那么 n 号乘客坐到自己座位的概率为 1
（为什么分母是 n - 1？ 因为 k 号座位被坐了，它必定不会去坐）
2、k 号有 1 / n - 1 的概率 坐到 n 号座位，那么 n 号 肯定坐不到 n 号座位，那么概率为 0
3、k 号有 n - 3 / n - 1 的概率坐到 除 1、k、n 外的座位，假设是 m 号座位
。。。
递归分析
当 n = 1 时，那么概率必定为 1
*/
if(n == 1){
return 1;
}
//注意不能直接写 1 / n, 否则结果直接为 0
return 1.0 / n + (double)(n - 2) / n * nthPersonGetsNthSeat(n - 1);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# 总结
- 分析出几种情况，然后分别对各个情况实现
