1227. Airplane Seat Assignment Probability

题目信息

题号:

1227

难度:

Medium

主题:

概率、递推、随机过程

原题:

LeetCode 1227

重点:

第一位乘客随机选座;后续乘客在自己的座位空闲时必坐自己的座位,否则从剩余座位中随机选择

题目重述

飞机有 n 个座位和 n 名按编号顺序登机的乘客,每名乘客都有对应座位。第一名乘客遗失了座位票,会从全部座位中等概率随机选择一个。

从第二名乘客开始,若自己的座位仍空闲,就坐自己的座位;否则从剩余空座中等概率随机选择一个。请返回第 n 名乘客最终坐到自己座位的概率。

1 <= n <= 10^5。

自建示例

乘客数不少于二时概率保持不变:

输入:n = 6
输出:0.5
解释:随机过程最终只取决于第一名乘客的座位和最后一名乘客的座位谁先被选中,两者概率相同。

只有一名乘客时必然坐到自己的座位:

输入:n = 1
输出:1.0
解释:唯一可选座位就是该乘客自己的座位。