约瑟夫环

题目

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

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

思路

• 对于「n, m 问题」，首轮删除环中第 m 个数字后，得到一个长度为 n - 1的数字环。由于有可能 m>n ，因此删除的数字为 (m−1)%n ，删除后的数字环从下个数字（即 m % n）开始，设 t=m%n ，可得数字环：t, t + 1, t + 2 ….. t - 3, t - 2
• 删除一轮后的数字环也变成一个[n - 1, m 问题] ，只是编号相对于从0开始的数字编号加了t
• 相当于[n - 1, m 问题]的数字x 相当于 （x + t）% n
• 所以，若已知[n - 1, m问题]的解为f(n - 1)，则
• 其中f(1) = 0恒定，作为状态初始值

  代码

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