1227. Airplane Seat Assignment Probability

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).

Note

1 <= n <= 10^5

题意 这个题的题意就是求最后一个人能够坐在自己的座位上的概率是多少。这个题的关键就是当最后一个人上来的时候,那么从第二个座位到第 n-1 个座位的位置都已经坐满了人。因为前面的人要么是别人占了自己的座位,自己随便挑一个别的位置,要么就是自己的位置是空白,自己坐自己的位置,那么剩下的位置就是 第一个和最后一个,这两个位置被之前的人选中的概率是相等的, 所以第n个人坐在自己的位置的概率是 1/2. follow up 第k个人上来,他做到自己位置上的概率是多少? 同理,对于第k个人来说,2 ~ (k-1)的位置上都坐满了人, 其余N−K+2个位置中有一个被占,而且概率相等,所以第K个人的座位被占的概率是1/(N−K+2). 带入 n 也能算出最后一个人做到自己位置的概率为1/2 代码

class Solution {
    public double nthPersonGetsNthSeat(int n) {
        if(n == 1) return 1;
        else return 0.5;
    }
}

Search

    Table of Contents