题目描述
n
个乘客乘坐有恰好 n
个座位的飞机。第一个乘客丢失了票所以随机选了一个作为,但之后剩余的乘客按照以下顺序乘坐:
- 如果他的座位空闲,则他会选他的座位。
- 否则随机选一个空闲的座位。
问第 n
个人能坐到自己座位的概率。
样例
输入:n = 1
输出:1.00000
解释:第一个乘客只能坐到自己的座位上。
输入:n = 2
输出:0.50000
解释:第二个乘客有 0.5 的概率坐到第二个座位上(当第一个乘客选了第一个座位)。
限制
1 <= n <= 10^5
算法
(数学) $O(1)$
- 通过条件概率,构造递推公式,假设 $n$ 个人的答案为 $f(n)$。已知 $f(1) = 1$。
- 假设现在有 $n$ 个人,如果第一个人选了 1 号座位,则第 $n$ 个人必定会坐到自己的座位上。这个事件发生的概率为 $\frac{1}{n}$。
- 如果第一个人选了 $n$ 号座位,则第 $n$ 个人永远不会坐到自己的座位上。这个事件发生的概率也为 $\frac{1}{n}$。
- 接下来,不妨假设第一个人选了 $j$ 号座位,其中 $2 \le j \le n - 1$,则第二个到第 $j - 1$ 个人都会坐到自己的座位上,第 $j$ 个人到第 $n$ 个人的座位有可能被打乱。此时,如果第 $j$ 个人选择了第一个人的座位,则第 $n$ 个人必定会坐到自己的座位上。如果第 $j$ 个人选了 $n$ 号座位,则第 $n$ 个人永远不会坐到自己的座位上,所以规模变成了 $n - j + 1$ 个人的问题。
- 综上,当 $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)$。
- 对于 $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$ 成立。
- $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;
}
};