1227. 飞机座位分配概率 | LeetCode算法题解

题目描述

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

剩下的乘客将会：

如果他们自己的座位还空着，就坐到自己的座位上，

当他们自己的座位被占用时，随机选择其他座位
第 n 位乘客坐在自己的座位上的概率是多少？

示例 1：

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

示例 2：

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

提示：

1 <= n <= 10^5

来源：LeetCode

首先是我是推导出一个递归的解法。
为了方便描述，我们设f = nthPersonGetsNthSeat。
从第一个人开始看，假如他坐在了自己的位置上，则后面的人会依次坐在自己的位置上，包括 n。这个概率是 1/n。
假入他坐在了 n 的位置，那无论后面人怎么坐，n 都不可能坐在自己的位置上，这个概率也是 1/n。
再看其他情况，假如他坐在了 2 号位，则 2 号只能随机挑别的，若 2 号恰好坐在了 1 号位，则后面的人又可以依次坐在自己的位置上。是不是和刚才的情况很像？
对了，这就转化成了第n-1的问题。这种情况 n 能坐对的概率是1/n * f(n - 1) 假如 1 坐在了 3、4、5、6、...、k 的位置，则 2 到 k-1 会依次坐在自己的位置，剩下的问题又转化为f(n - k)，此时 n 能坐对的概率是1/n * f(n - k)
于是可得递归的解法，f(n) = (f(1) + f(2) + ... + f(n-1))/n。为了避免大量重复的计算，我们用一个map将f(n)的结果存储起来。

测试的时候发现，很多用例得到的结果都是0.5，感觉有点奇怪，但还是先提交试试。

很不幸，测试n=100000的时候，堆栈溢出了。

const map = { 1: 1 };

/**
 * @param {number} n
 * @return {number}
 */
const nthPersonGetsNthSeat = n => {
  if (map[n]) return map[n];

  let accumulate = 0;

  for (let k = 1; k <= n - 1; k++) {
    accumulate += nthPersonGetsNthSeat(k);
  }

  const result = accumulate / n;

  map[n] = result;

  return result;
};

数学方法

/**
 * @param {number} n
 * @return {number}
 */
const nthPersonGetsNthSeat = n => {
  return n === 1 ? 1 : 0.5;
};

题目描述

思路

递归

数学

解法

递归方法

数学方法