题目描述

n 个乘客乘坐有恰好 n 个座位的飞机。第一个乘客丢失了票所以随机选了一个作为，但之后剩余的乘客按照以下顺序乘坐：

• 如果他的座位空闲，则他会选他的座位。
• 否则随机选一个空闲的座位。

问第 n 个人能坐到自己座位的概率。

样例

输入：n = 1
输出：1.00000
解释：第一个乘客只能坐到自己的座位上。

输入：n = 2
输出：0.50000
解释：第二个乘客有 0.5 的概率坐到第二个座位上（当第一个乘客选了第一个座位）。

限制

• 1 <= n <= 10^5

算法

(数学) $O(1)$

1. 通过条件概率，构造递推公式，假设 $n$ 个人的答案为 $f(n)$。已知 $f(1) = 1$。
2. 假设现在有 $n$ 个人，如果第一个人选了 1 号座位，则第 $n$ 个人必定会坐到自己的座位上。这个事件发生的概率为 $\frac{1}{n}$。
3. 如果第一个人选了 $n$ 号座位，则第 $n$ 个人永远不会坐到自己的座位上。这个事件发生的概率也为 $\frac{1}{n}$。
4. 接下来，不妨假设第一个人选了 $j$ 号座位，其中 $2 \le j \le n - 1$，则第二个到第 $j - 1$ 个人都会坐到自己的座位上，第 $j$ 个人到第 $n$ 个人的座位有可能被打乱。此时，如果第 $j$ 个人选择了第一个人的座位，则第 $n$ 个人必定会坐到自己的座位上。如果第 $j$ 个人选了 $n$ 号座位，则第 $n$ 个人永远不会坐到自己的座位上，所以规模变成了 $n - j + 1$ 个人的问题。
5. 综上，当 $n \ge 2$ 时，递推公式可以为 $f(n) = \frac{1}{n} \cdot 1 + \frac{1}{n} \cdot 0 + \frac{1}{n} \cdot \sum_{j=2}^{n-1} f(n - j + 1) = \frac{1}{n} \sum_{j=1}^{n-1} f(j)$。即 $(n + 1) \cdot f(n) = \sum_{j=2}^{n} f(j)$。
6. 对于 $n \ge 2$ 时，又有 $(n + 2) \cdot f(n + 1) = \sum_{j=2}^{n+1} f(j)$，通过等式相减，可以得到 $(n + 1) \cdot f(n + 1) = (n + 1) \cdot f(n)$。已知 $f(n) \neq 0$，所以 $f(n) = f(n + 1)$ 对 $n \ge 2$ 成立。
7. $f(2) = 0.5$，所以当 $n \ge 2$ 时，$f(n) = 0.5$。

时间复杂度

• 直接判断 $n$ 是否大于 1，所以时间复杂度为常数。

空间复杂度

• 显然为常数的空间。

C++ 代码

class Solution {
public:
    double nthPersonGetsNthSeat(int n) {
        return n > 1 ? 0.5 : 1;
    }
};