Leetcode 1823 找出游戏的获胜者 (约瑟夫环问题)

约瑟夫环：1....n的数字围成一个圈，依次数数，到第K位的时候，从环里移除这个数字，直到剩余最后一个数字。

解法1：模拟，容易超时(不推荐)

解法2：倒推。时间复杂度O(n)

倒推思路：从最后的状态往前推导。

状态N，只有1个数字P，P数字的位置是0号位置。（P就是我们求得目标数字）

状态N-1，只有2个数字，其中有数字P，此时的P的位置要么0,要么1，根据K我们可以求得此时状态的P的位置。

状态N-2，只有3个数字，其中有数字P，此时P的位置在0,1,2。

以此类推......

初始状态，只有N个数字，其中有数字P，P的位置在0...N-1的位置。(此时P的位置就是我们要的结果)

这里必须注意：每个状态的起始计数位置是0号位置。

为了看起来更加直观，这里贴上一个例子: 以N = 5, K = 2为例。

表格1是倒推的状态图 表格2是正推的状态图 正推的过程是：2号位置每次都移除，然后从后面的位置重新开始计数，所以当从0数到k-1的时候，K的位置变成了0号位置。

各状态间的关系:

根据上面的分析，我们可以再将各个状态的关系进行梳理:

P(N) = 0 初始状态，数字P在0号位置。只有一个数字P。 上一个状态N-1就是(P(N) + k) % 2，即N-1状态移除了一个数字，这个移除的数字+P(N)就是当前状态N-1的P的位置，因为是环所以需要mod(总数字个数) 所以P(n-1） = (P(N) + k) % 2

所以得出结论：

P(n) = 0 P(n-1) = (P(n) + K) % 2 P(n-2) = (P(n-1) + k) % 3 依次类推 得到P(1) = (P(2) + K) % n

class Solution {
    public int findTheWinner(int n, int k) {
        int pos = 0;
        //倒推法
        for(int i=2;i<=n;i++) {
            pos =(pos + k) % i;
        }
        return pos + 1;
    }
}