[LeetCode] 1227. Airplane Seat Assignment Probability

[grandyang]

n passengers board an airplane with exactly n seats. The first passenger has lost the ticket and picks a seat randomly. But after that, the rest of passengers will:

• Take their own seat if it is still available,
• Pick other seats randomly when they find their seat occupied

What is the probability that the n-th person can get his own seat?

Example 1:

Input: n = 1
Output: 1.00000
Explanation: The first person can only get the first seat.

Example 2:

Input: n = 2
Output: 0.50000
Explanation: The second person has a probability of 0.5 to get the second seat (when first person gets the first seat).

Constraints:

• 1 <= n <= 10^5

这道题说是有n个人要登机，且飞机上正好有n个座位，说是第一个人会在n个座位中随机选一个位置坐，然后从第二个人开始，遵循这样的选座方法：若其对应的座位号是空的，则坐到自己的位置，否则就在剩余的位置中随机挑选一个位置坐，现在问第n个人能坐到自己的位置的概率是多少。这道题其实没有太多的算法在里面，本质上其实是一道数学题，一般来说这种类似脑筋急转弯的题目在数学推导方面完成了之后，代码可能就非常的简单了，甚至一两行就可以搞定了，但难点就是在于数学推导的部分。现在来分析一下吧，由于第一个人是随机挑选座位，其挑选的座位对后面的人的影响是不同的，需要分情况来讨论：

• 当第一个人正好选到了自己的座位时，这种情况的概率是 1/n，那么对于之后的所有人来说，自己的座位都是空的，可以直接坐，那么每个人坐到自己位子的概率也就是第一个人坐到自己位置的概率，都为 1/n（包括第n个人）。

• 当第一个人直接一勾子坐到第n个座位上（概率是 1/n），那么不管中间的人怎么坐，第n个人都无法再坐到自己的位置上了，概率为0。

• 当第一个人坐到了范围 [2, n-1] 中的任意一个位置，共有的 n-2 个位置可供选择，到达这种情况的总概率是 (n-2)/n，但坐到每一个位子的概率还是 1/n。若第一个人坐到了第二个位子，第二个人此时就有三种选择：1）坐到第一个人的位子，则之后所有的人都可以坐到自己的位子了，包括第n个人，概率是 (n-2)/n * 1/(n-2)。2）坐到第n个座位，则第n个人就无法坐自己位子了，概率是0。3）坐其他的座位，范围是 [1, 1] 并 [3, n-1]，这里还是得分情况讨论，有没有没发现，这三种情况其实就是对应着第一个人开始的三种情况，也就是说当前实际上就变成了一个共 n-1 个座位的子问题，此时第二个人就相当于变成了第一个人，但可能有的童鞋会有疑问，不对吧，此时的第二个人不能坐自己的位置，而第一个人开始是可以坐自己的位置的，两人的情况不同啊，怎么能说是子问题呢？其实看是不是子问题，主要是看对所求的结果是否有影响，求的只是第n个人能坐到自己位置的概率，即便第二个人不能坐自己的位置，但是可以坐第一个人的位置，那么就相当于前两个人都坐了自己的位置，对后面的人没有影响，所以可以看作是子问题，这种情况的概率是 (n-2)/n * 1/(n-2) * f(n-1)。当第一个人坐到第三个位子的时候，那么第二个人就可以坐自己的位置，第三个人实际又面临相同的三个选择，此时就是共有 n-2 个座位的子问题, 这种情况的概率是 (n-2)/n * 1/(n-2) * f(n-2)，后面都是依次类推。

所以，整个的概率可以写为如下表达式：

f(n) = 1/n + 0 + (n-2)/n * (1/(n-2) * f(n-1) + 1/(n-2) * f(n-2) + ... + 1/(n-2) * f(2))

化简一下可得：

f(n) = 1/n + 1/n * (f(n-1) + f(n-2) + ... + f(2))

注意这是n大于2的情况，n小于等于2的时候，可以直接分析出来，就是 0.5。现在的目标是要化简上面的表达式，首先两边同时乘以n，可以得到：

n * f(n) = 1 + f(n-1) + f(n-2) + ... + f(2)

把上面这个称作公式1，然后将上面公式中的n用 n-1 替换，可以得到公式2:

(n-1) * f(n-1) = 1 + f(n-2) + f(n-3) + ... + f(2)

然后用公式1减去公式2，可以得到：

n * f(n) - (n-1) * f(n-1) = f(n-1)

化简后可得：

f(n) = f(n-1)

我们已经知道 f(2) = 0.5，那么根据上面这个式子，就可以知道任何大于2的n的函数值都是 0.5，所以这道题也就一行代码搞定了，参见代码如下：

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

Github 同步地址:

#1227

参考资料：

https://leetcode.com/problems/airplane-seat-assignment-probability/

https://leetcode.com/problems/airplane-seat-assignment-probability/discuss/414864/True-formula-and-explanations-for-all-other-formulas.

https://leetcode.com/problems/airplane-seat-assignment-probability/discuss/411905/It's-not-obvious-to-me-at-all.-Foolproof-explanation-here!!!-And-proof-for-why-it's-12

LeetCode All in One 题目讲解汇总(持续更新中...)