Skip to content

Latest commit

 

History

History
182 lines (126 loc) · 5.46 KB

File metadata and controls

182 lines (126 loc) · 5.46 KB

English Version

题目描述

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&gt;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} $$

Python3

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

Java

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

C++

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

Go

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

...