1227. 飞机座位分配概率

• 标签：脑筋急转弯、数学、动态规划、概率与统计
• 难度：中等

题目链接

• 1227. 飞机座位分配概率 - 力扣

题目大意

描述：给定一个整数 $n$，代表 $n$ 位乘客即将登飞机。飞机上刚好有 $n$ 个座位。第一位乘客的票丢了，他随便选择了一个座位坐下。则剩下的乘客将会：

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

要求：计算出第 $n$ 位乘客坐在自己座位上的概率是多少。

说明：

• $1 \le n \le 10^5$。

示例：

• 示例 1：

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

• 示例 2：

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

解题思路

思路 1：数学

我们按照乘客的登机顺序为乘客编下号：$1 \sim n$，我们用 $f(n)$ 来表示第 $n$ 位乘客登机时，坐在自己座位上的概率。先从简单的情况开始考虑：

当 $n = 1$ 时：

• 第 $1$ 位乘客只能坐在第 $1$ 个座位上，$f(1) = 1$。

当 $n = 2$ 时：

• 第 $1$ 位乘客有 $\frac{1}{2}$ 的概率选中自己的位置，第 $2$ 位乘客一定能坐到自己的位置上，则第 $2$ 位乘客坐在自己座位上的概率为 $\frac{1}{2} * 1.0$。
• 第 $1$ 位乘客有 $\frac{1}{2}$ 的概率坐在第 $2$ 位乘客的位置上，第 $2$ 位乘客只能坐到第 $1$ 位乘客的位置上，那么第 $2$ 位乘客坐在自己座位上的概率为 $\frac{1}{2} * 0.0$。
• 综上，$f(2) = \frac{1}{2} * 1.0 + \frac{1}{2} * 0.0 = 0.5$。

当 $n \ge 3$ 时：

• 先来考虑第 $1$ 位乘客登机情况：

  • 第 $1$ 位乘客有 $\frac{1}{n}$ 的概率选择坐在自己位置上，这样第 $1$ 位到第 $n - 1$ 位乘客的座位都不会被占，第 n 位乘客一定能坐到自己位置上。那么第 n 位乘客坐在自己座位上的概率为 $\frac{1}{n} * 1.0$。

  • 第 $1$ 位乘客有 $\frac{1}{n}$ 的概率选择坐在第 $n$ 位乘客的位置上，这样第 $2$ 位到第 $n - 1$ 位乘客的座位都不会被占，第 $n$ 位乘客只能坐到第 $1$ 位乘客的位置上，那么第 $n$ 位乘客坐在自己座位上的概率为 $\frac{1}{n} * 0.0$。

  • 第 $1$ 位乘客有 $\frac{n-2}{n}$ 的概率坐在第 $i$ 号座位上，$2 \le i \le n - 1$，每个座位被选中概率为 $\frac{1}{n}$。这样第 $2$ 位到第 $i - 1$ 位乘客的座位都不会被占。此时第 $i$ 位乘客，会在剩下的 $n - (i - 1)$ 个座位中进行选择：

    • 坐在第 $1$ 位乘客的位置上，这样后面的乘客座位都不会被占，第 $n$ 位乘客一定能坐到自己位置上。

    • 坐在第 $n$ 个乘客的位置上，这样第 $n$ 个乘客肯定无法坐到自己的位置上。

    • 在第 $[i + 1, n - 1]$ 之间找个位置坐。

• 再来考虑第 $i$ 位乘客登机情况：

  • 第 $i$ 为乘客所面临的情况跟第 $1$ 位乘客所面临的情况类似，只不过问题的规模数从 $n$ 减小到了 $n - (i - 1)$。

那么综合上面情况，可以得到 $f(n),(n \ge 3)$ 的递推式：

$\begin{aligned} f(n) & = \frac{1}{n} * 1.0 + \frac{1}{n} * 0.0 + \frac{1}{n} * \sum_{i = 2}^{n-1} f(n - i + 1) \cr & = \frac{1}{n} (1.0 + \sum_{i = 2}^{n-1} f(n - i + 1)) \end{aligned}$

接下来我们从等式中寻找规律，消去 $\sum_{i = 2}^{n-1} f(n - i + 1)$ 部分。

将 $n$ 换为 $n - 1$，得：

$\begin{aligned} f(n - 1) & = \frac{1}{n - 1} * 1.0 + \frac{1}{n - 1} * 0.0 + \frac{1}{n - 1} * \sum_{i = 2}^{n-2} f(n - i) \cr & = \frac{1}{n - 1} (1.0 + \sum_{i = 2}^{n-2} f(n - i)) \end{aligned} $

将 $f(n) * n$ 与 $f(n - 1) * (n - 1)$ 进行比较：

$\begin{aligned} f(n) * n & = 1.0 + \sum_{i = 2}^{n-1} f(n - i + 1) & (1) \cr f(n - 1) * (n - 1) & = 1.0 + \sum_{i = 2}^{n-2} f(n - i) & (2) \end{aligned}$

将上述 (1)、(2) 式相减得：

$\begin{aligned} & f(n) * n - f(n - 1) * (n - 1) & \cr = & \sum_{i = 2}^{n-1} f(n - i + 1) - \sum_{i = 2}^{n-2} f(n - i) \cr = & f(n-1) \end{aligned}$

整理后得：$f(n) = f(n - 1)$。

已知 $f(1) = 1$，$f(2) = 0.5$，因此当 $n \ge 3$ 时，$f(n) = 0.5$。

所以可以得出结论：

$f(n) = \begin{cases} 1.0 & n = 1 \cr 0.5 & n \ge 2 \end{cases}$

思路 1：代码

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

思路 1：复杂度分析

• 时间复杂度：$O(1)$。
• 空间复杂度：$O(1)$。

参考资料

• 飞机座位分配概率 - 力扣（LeetCode）