力扣挑战赛第3天-No.1227飞机座位分配概率

题目描述

有 n 位乘客即将登机，飞机正好有 n 个座位。第一位乘客的票丢了，他随便选了一个座位坐下。

剩下的乘客将会：

• 如果他们自己的座位还空着，就坐到自己的座位上，
• 当他们自己的座位被占用时，随机选择其他座位

第 n 位乘客坐在自己的座位上的概率是多少？

示例：

输入：n = 1
输出：1.00000
解释：第一个人只会坐在自己的位置上。

输入: n = 2
输出: 0.50000
解释：在第一个人选好座位坐下后，第二个人坐在自己的座位上的概率是 0.5。

注意：

1 <= n <= 10^5

解法

推导过程：

设第 n 位乘客坐在自己的座位上的概率为 f(n)

第一位乘客因票丢失，面临如下情况：

• 他有 1 / n 的概率坐到正确的座位，则后面的乘客都会坐到自己的座位上，所以 f(n)’ = 1 / n；
• 他有 1 / n 的概率坐到第 n 位乘客的座位，则后面的乘客除了第 n 位都会坐到自己的座位上，而第 n 位乘客只能坐到第 1 位乘客的位置，所以 f(n)’ = 0；
• 他有 1 / n 的概率坐到第 i 位乘客的座位，其中 2 <= i <= n - 1，则第 2 到 i - 1 位乘客都能坐到自己的座位上，而当第 i 位乘客来到客舱，发现自己的座位被人（第 1 位乘客）占了，这时他会从剩下的 n - i + 1 随机选择一个座位坐下，因此他面临的情况和第 1 位乘客一样，只不过此时的第一种情况下，正确的座位是第 1 位乘客的座位，所以 f(n)’ = f(n - i + 1)；

由此可以得到递推式：

f(n) = 1 / n * (1 + 0 + SUM[2, n-1] f(n - i + 1))，其中SUM[2, n-1]表示i从2到n-1对后面的式子进行求和

令 n = n - 1，则

f(n - 1) = 1 / (n - 1) * (1 + 0 + SUM[2, n-2] f(n - i))

两式相减得：n * f(n) - (n - 1) * f(n - 1) = f(n - 1)，即 f(n) = f(n - 1) = …… = f(2)

因此，对任意 n >= 2，有 f(n) = f(2) = 0.5，当 n = 1，f(n) = 1

/**
 * @param {number} n
 * @return {number}
 */
const nthPersonGetsNthSeat = function(n) {
  return n === 1 ? 1 : .5;
};

Donate