难度: Medium
有 n 位乘客即将登机，飞机正好有 n 个座位。第一位乘客的票丢了，他随便选了一个座位坐下。
剩下的乘客将会：
如果他们自己的座位还空着，就坐到自己的座位上，
第 n 位乘客坐在自己的座位上的概率是多少？
示例 1：
输入：n = 1 输出：1.00000 解释：第一个人只会坐在自己的位置上。
示例 2：
输入: n = 2 输出: 0.50000 解释：在第一个人选好座位坐下后，第二个人坐在自己的座位上的概率是 0.5。
提示：
1 <= n <= 10^5运行时间: 24 ms
内存: 16.1 MB
class Solution:
def nthPersonGetsNthSeat(self, n: int) -> float:
return 1 if n==1 else .5
这个问题可以通过递归思维来解决，但它的美在于可以简化为一个非常直观的数学问题。考虑两种情况： 1. 当只有一位乘客时，他只能坐在自己的座位上，所以概率是 1。 2. 当有多于一位乘客时，第一个乘客随机选择一个座位，这个选择将影响最后一位乘客能否坐在自己的座位上。第一个乘客可能坐在第一个座位上，可能坐在最后一个座位上，或者坐在中间的任何一个座位上。如果第一个乘客坐在最后一个座位上，那么最后一个乘客不能坐在自己的座位上。如果第一个乘客坐在第一个座位上，那么每个人都能坐在自己的座位上。如果第一个乘客坐在中间的某个座位上，这将触发一系列随机选择，但最终结果的概率总是趋向于 0.5，因为这变成了两个等可能的结果：最后一个乘客的座位被占用或未被占用。
时间复杂度: O(1)
空间复杂度: O(1)
# 定义解决方案类
class Solution:
# 定义函数，接收整数 n 作为唯一参数
def nthPersonGetsNthSeat(self, n: int) -> float:
# 当只有一位乘客时，返回 1.0（因为他只能坐在自己的座位上）
if n == 1:
return 1.0
# 当有多于一位乘客时，返回 0.5（根据上述逻辑推导结果）
else:
return 0.5
当第一个乘客选择中间的座位i（非第一个也非最后一个座位），接下来的乘客会面临两种情况：他们的座位被占用或者未被占用。如果被占用，他们可能会选择其他任何未被占用的座位。这样的选择持续进行直到最后一个乘客。在这一系列的随机选择中，最终只关注两个特殊的座位：第一个乘客选择的座位i和最后的座位n。由于每次座位的选择都是随机的，分析到最后一个乘客时，他的座位n要么是被第一个乘客占据的座位i，要么是其他未被选择的座位。因此，这里有两种可能：最后一个座位是空的（未被占用），或者已被之前的某个乘客占用。这两种情况是等可能的，因此最后一个乘客的座位被占用与未被占用的概率均为0.5。
题解中的情况考虑了中间乘客的选择，但当第一位乘客直接坐在最后一个座位上时，这个座位已经被占用，因此最后一位乘客无法坐在自己的座位上。中间的乘客虽有选择，但他们的选择不会改变最后一个座位已被占用这一事实。
是的，这种方法适用于所有输入范围，包括非常大的n值。因为逻辑不依赖于具体的乘客数量，而是依赖于随机选择的性质和递归的结构。无论n的大小如何，最后一个乘客坐在自己座位的概率始终是0.5（除了n为1的特殊情况）。因此，这种方法对于大规模输入也是有效的。
当n为1时，即只有一位乘客，那么无论他是否记得自己的座位位置，由于飞机上只有一个座位可用，他只能坐在这个座位上。因此，无论是否丢失了票或忘记了座位号，最终他坐在自己座位上的概率仍然是100%。