圆圈中最后剩下的数字

0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。

例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

示例 1：

输入: n = 5, m = 3 输出: 3 示例 2：

输入: n = 10, m = 17 输出: 2  

限制：

1 <= n <= 10^5 1 <= m <= 10^6

分析

这其实就是著名的约瑟夫问题。

简单的解法可以用循环单链表来解决，时间复杂度是O(m*n)。

还可以使用动态规划的解法，能将时间复杂度降低到O(N)，空间复杂度为O(1)。

设n个数字最后剩下数字的结果为f(n)，那么：

• n，m 问题，数环0，1，2...，n-1，解为f(n)
• n-1，m 问题，数环0，1，2...，n-2，解为f(n-1)

以n=5,m=3为例子，n=5姑且转换看成数组[0, 1, 2, 3, 4]，第一次删除数字，即删除第三个数字2，那么下一次要从3开始数起，再对比原数组：

0, 1, 2, 3 // 4就不放进来了
3, 4, 0, 1 

仔细思考一下，这里有个对应关系，设x是数组中的某一个数字，有关系y=(x+m)，比如3=0+3。

注意到m是可以大于n的，所以y=(x+m)%n。

我们知道，在[3, 4, 0, 1]中，必定有个位置上数是最后我们要的结果（循环再做几次，我们知道结果f(5)是开头位置上的3），跟数组中的数字没有任何关系，只跟数组长度和m有关系。

所以就算把[3, 4, 0, 1]换成[0, 1, 2, 3]，最后结果依然是第一个位置上的数字，即0。

然后我们可以惊奇地发现对于数组[0, 1, 2, 3]，其实不就是求f(4)的问题么？间接就能得到[3, 4, 0, 1]循环删除后剩下数字是第一个位置上的数，即3，也就是f(5)的结果。

那么f(5)和f(4)的关系为f(5)=(f(4)+m)%n，推导得出动态方程f(n)=(f(n-1)+m)%n。

当n=0的时候，初始值dp[0]=0。

代码：

class Solution {
    public int lastRemaining(int n, int m) {
        int dp[] = new int[n+1];
        dp[1] = 0;
        for (int i=2; i<=n; i++) {
            dp[i] = (dp[i-1] + m) % i;
        }
        return dp[n];
    }
}

空间优化：

class Solution {
    public int lastRemaining(int n, int m) {
        int res = 0;
        for (int i=2; i<=n; i++) {
            res = (res + m) % i;
        }
        return res;
    }
}