1227. 飞机座位分配概率

题目描述

有 n 位乘客即将登机，飞机正好有 n 个座位。第一位乘客的票丢了，他随便选了一个座位坐下。

剩下的乘客将会：

如果他们自己的座位还空着，就坐到自己的座位上，
当他们自己的座位被占用时，随机选择其他座位

第 n 位乘客坐在自己的座位上的概率是多少？

示例 1：

输入：n = 1
输出：1.00000
解释：第一个人只会坐在自己的位置上。

示例 2：

输入: n = 2
输出: 0.50000
解释：在第一个人选好座位坐下后，第二个人坐在自己的座位上的概率是 0.5。

提示：

1 <= n <= 10^5

解法

方法一：数学

用 \(f(n)\) 表示当有 \(n\) 位乘客登机时，第 \(n\) 位乘客坐在自己的座位上的概率。从最简单的情况开始考虑：

当 \(n=1\) 时，只有 \(1\) 位乘客和 \(1\) 个座位，因此第 \(1\) 位乘客只能坐在第 \(1\) 个座位上，\(f(1)=1\)；

当 \(n=2\) 时，有 \(2\) 个座位，每个座位有 \(0.5\) 的概率被第 \(1\) 位乘客选中，当第 \(1\) 位乘客选中座位之后，第 \(2\) 位乘客只能选择剩下的座位，因此第 \(2\) 位乘客有 \(0.5\) 的概率坐在自己的座位上，\(f(2)=0.5\)。

当 \(n>2\) 时，如何计算 \(f(n)\) 的值？考虑第 \(1\) 位乘客选择的座位，有以下三种情况。

第 \(1\) 位乘客有 \(\frac{1}{n}\) 的概率选择第 \(1\) 个座位，则所有乘客都可以坐在自己的座位上，此时第 \(n\) 位乘客坐在自己的座位上的概率是 \(1.0\)。
第 \(1\) 位乘客有 \(\frac{1}{n}\) 的概率选择第 \(n\) 个座位，则第 \(2\) 位乘客到第 \(n-1\) 位乘客都可以坐在自己的座位上，第 \(n\) 位乘客只能坐在第 \(1\) 个座位上，此时第 \(n\) 位乘客坐在自己的座位上的概率是 \(0.0\)。
第 \(1\) 位乘客有 \(\frac{n-2}{n}\) 的概率选择其余的座位，每个座位被选中的概率是 \(\frac{1}{n}\)。假设第 \(1\) 位乘客选择第 \(i\) 个座位，其中 \(2 \le i \le n-1\)，则第 \(2\) 位乘客到第 \(i-1\) 位乘客都可以坐在自己的座位上，第 \(i\) 位乘客到第 \(n\) 位乘客的座位不确定，第 \(i\) 位乘客会在剩下的 \(n-(i-1)=n-i+1\) 个座位中随机选择（包括第 \(1\) 个座位和第 \(i+1\) 个座位到第 \(n\) 个座位）。由于此时剩下的乘客数和座位数都是 \(n-i+1\)，有 \(1\) 位乘客会随机选择座位，因此问题规模从 \(n\) 减小至 \(n-i+1\)。

结合上述三种情况，可以得到 \(f(n)\) 的递推式：

\[ \begin{aligned} f(n) &= \frac{1}{n} \times 1.0 + \frac{1}{n} \times 0.0 + \frac{1}{n} \times \sum_{i=2}^{n-1} f(n-i+1) \\ &= \frac{1}{n}(1.0+\sum_{i=2}^{n-1} f(n-i+1)) \end{aligned} \]

上述递推式中，\(i\) 的取值个数有 \(n-2\) 个，由于 \(i\) 的取值个数必须是非负整数，因此只有当 \(n-2 \ge 0\) 即 \(n \ge 2\) 时，上述递推式才成立。

如果直接利用上述递推式计算 \(f(n)\) 的值，则时间复杂度为 \(O(n^2)\)，无法通过全部测试用例，因此需要优化。

将上述递推式中的 \(n\) 换成 \(n-1\)，可以得到递推式：

\[ f(n-1) = \frac{1}{n-1}(1.0+\sum_{i=2}^{n-2} f(n-i)) \]

上述递推式中，\(i\) 的取值个数有 \(n-3\) 个，只有当 \(n-3 \ge 0\) 即 \(n \ge 3\) 时，上述递推式才成立。

当 \(n \ge 3\) 时，上述两个递推式可以写成如下形式：

\[ \begin{aligned} n \times f(n) &= 1.0+\sum_{i=2}^{n-1} f(n-i+1) \\ (n-1) \times f(n-1) &= 1.0+\sum_{i=2}^{n-2} f(n-i) \end{aligned} \]

将上述两式相减：

\[ \begin{aligned} &~~~~~ n \times f(n) - (n-1) \times f(n-1) \\ &= (1.0+\sum_{i=2}^{n-1} f(n-i+1)) - (1.0+\sum_{i=2}^{n-2} f(n-i)) \\ &= \sum_{i=2}^{n-1} f(n-i+1) - \sum_{i=2}^{n-2} f(n-i) \\ &= f(2)+f(3)+...+f(n-1) - (f(2)+f(3)+...+f(n-2)) \\ &= f(n-1) \end{aligned} \]

整理后得到简化的递推式：

\[ \begin{aligned} n \times f(n) &= n \times f(n-1) \\ f(n) &= f(n-1) \end{aligned} \]

由于已知 \(f(1)=1\) 和 \(f(2)=0.5\)，因此当 \(n \ge 3\) 时，根据 \(f(n) = f(n-1)\) 可知，对任意正整数 \(n\) 都有 \(f(n)=0.5\)。又由于 \(f(2)=0.5\)，因此当 \(n \ge 2\) 时，对任意正整数 \(n\) 都有 \(f(n)=0.5\)。

由此可以得到 \(f(n)\) 的结果：

\[ f(n) = \begin{cases} 1.0, & n = 1 \\ 0.5, & n \ge 2 \end{cases} \]

时间复杂度 \(O(1)\)，空间复杂度 \(O(1)\)。

Python3JavaC++GoTypeScriptRust

class Solution:
    def nthPersonGetsNthSeat(self, n: int) -> float:
        return 1 if n == 1 else 0.5

class Solution {
    public double nthPersonGetsNthSeat(int n) {
        return n == 1 ? 1 : .5;
    }
}

class Solution {
public:
    double nthPersonGetsNthSeat(int n) {
        return n == 1 ? 1 : .5;
    }
};

func nthPersonGetsNthSeat(n int) float64 {
    if n == 1 {
        return 1
    }
    return .5
}

function nthPersonGetsNthSeat(n: number): number {
    return n === 1 ? 1 : 0.5;
}

impl Solution {
    pub fn nth_person_gets_nth_seat(n: i32) -> f64 {
        return if n == 1 { 1.0 } else { 0.5 };
    }
}

1227. 飞机座位分配概率

题目描述

解法

方法一：数学

评论