有 n 位乘客即将登机,飞机正好有 n 个座位。第一位乘客的票丢了,他随便选了一个座位坐下。
剩下的乘客将会:
如果他们自己的座位还空着,就坐到自己的座位上,
当他们自己的座位被占用时,随机选择其他座位 第 n 位乘客坐在自己的座位上的概率是多少?
示例 1:
输入:n = 1
输出:1.00000
解释:第一个人只会坐在自己的位置上。
示例 2:
输入: n = 2
输出: 0.50000
解释:在第一个人选好座位坐下后,第二个人坐在自己的座位上的概率是 0.5。
提示:
- 1 <= n <= 10^5
思路分析:
- 基本情况:当 n = 1 时,只有一名乘客,他必然坐在自己的座位上,因此概率是 1。
- 一般情况:当 n > 1 时,第一位乘客随机选择了一个座位。对于第二位乘客来说,如果他坐在了第一位乘客的座位上,那么第一位乘客的座位就不再是自己的了。因此,第二位乘客坐在自己座位上的唯一情况是,第一位乘客选择了除第二位乘客的座位之外的其他座位。
- 计算概率:当有两位乘客时,第一位乘客随机选择座位,第二位乘客坐在自己座位上的概率是 1/2,因为第一位乘客有 2 个选择(自己的座位和其他座位),而只有 1 个选择(其他座位)会导致第二位乘客坐在自己的座位上。
- 推广:对于超过两位乘客的情况,我们可以观察到,一旦第一位乘客坐下来,剩下的每位乘客都有一半的概率坐在自己的座位上,前提是他们之前的乘客没有坐在他们的座位上。因此,对于 n 位乘客,第一位乘客坐下来后,第二位乘客坐在自己座位上的概率是 1/2,第三位乘客也坐在自己座位上的概率是 1/2,以此类推。这些事件是独立的,因此最终所有乘客都坐在自己座位上的概率是 1/2 的 n-1 次方。
- 特殊情况:当 n = 2 时,根据上述分析,概率是 1/2。
时间复杂度:O(1),算法直接返回结果,不需要任何循环或递归。 空间复杂度:O(1),算法只使用了常量级别的额外空间。
var nthPersonGetsNthSeat = function (n) {
return n == 1 ? 1.0 : 0.5;
};