飞机座位分配概率

/*
 * 思路：
 * Java Stream不太适合这种简单的数学归纳问题，因此直接使用简单的if判断。
 */
import java.util.stream.IntStream;

public class Solution {
    public double nthPersonGetsNthSeat(int n) {
        return IntStream.of(n).mapToDouble(i -> i == 1 ? 1.0 : 0.5).findFirst().orElse(0.5);
    }
}

这个问题可以通过递归思维来解决，但它的美在于可以简化为一个非常直观的数学问题。考虑两种情况： 1. 当只有一位乘客时，他只能坐在自己的座位上，所以概率是 1。 2. 当有多于一位乘客时，第一个乘客随机选择一个座位，这个选择将影响最后一位乘客能否坐在自己的座位上。第一个乘客可能坐在第一个座位上，可能坐在最后一个座位上，或者坐在中间的任何一个座位上。如果第一个乘客坐在最后一个座位上，那么最后一个乘客不能坐在自己的座位上。如果第一个乘客坐在第一个座位上，那么每个人都能坐在自己的座位上。如果第一个乘客坐在中间的某个座位上，这将触发一系列随机选择，但最终结果的概率总是趋向于 0.5，因为这变成了两个等可能的结果：最后一个乘客的座位被占用或未被占用。

O(1)

O(1)