1227. 飞机座位分配概率

Medium

题目描述

n 个乘客准备登机，飞机正好有 n 个座位。第一个乘客丢失了机票，随机选择了一个座位坐下。

从第二个乘客开始，他们会按以下规则坐座位：

• 如果他们的座位还空着，就坐自己的座位
• 如果他们的座位被占了，就随机选择其他空座位

求第 n 个乘客坐到自己座位的概率。

示例 1：

输入：n = 1
输出：1.00000
解释：第一个乘客只能坐第一个座位。

示例 2：

输入：n = 2
输出：0.50000
解释：第二个乘客有 50% 的概率坐到第二个座位（当第一个乘客坐到第一个座位时）。

约束条件：

• 1 <= n <= 10^5

提示：

• 设 f(n) 表示 n 个人情况下第 n 个人坐到正确座位的概率
• f(1) = 1（基本情况）
• f(2) = 1/2（也是基本情况）
• 对于 i >= 2，f(i) = 1/2

解题思路

这是一个经典的概率论脑筋急转弯问题。我们可以通过数学归纳和递归分析来解决。

关键观察： 对于任意 n ≥ 2，第 n 个乘客坐到自己座位的概率都是 1/2。

数学分析： 考虑第一个乘客的行为：

• 如果他坐自己的座位（概率 1/n），那么后续所有乘客都能坐自己的座位，第 n 个人概率为 1
• 如果他坐第 n 个人的座位（概率 1/n），那么第 n 个人肯定坐不到自己座位，概率为 0
• 如果他坐第 k 个人的座位（2 ≤ k ≤ n-1，概率 1/n），那么前 k-1 个人都能坐自己座位，第 k 个人面临和第一个人相同的选择困境

递归思考： 当第 k 个人发现自己座位被占时，他只能在第 1 个座位和第 n 个座位中随机选择（其他座位都有主人会来认领）。这样问题就递归回到了原始状态。

因此，除了 n=1 的特殊情况外，答案总是 1/2。

简化解法： 通过数学证明可以得出：当 n=1 时返回 1.0，当 n≥2 时返回 0.5。

代码实现

class Solution {
public:
    double nthPersonGetsNthSeat(int n) {
        return n == 1 ? 1.0 : 0.5;
    }
};

class Solution:
    def nthPersonGetsNthSeat(self, n: int) -> float:
        return 1.0 if n == 1 else 0.5

public class Solution {
    public double NthPersonGetsNthSeat(int n) {
        return n == 1 ? 1.0 : 0.5;
    }
}

/**
 * @param {number} n
 * @return {number}
 */
var nthPersonGetsNthSeat = function(n) {
    if (n === 1) return 1.0;
    return 0.5;
};

复杂度分析