62.圆圈中最后剩下的数字 (Medium)*

题目描述*

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

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

限制*

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

代码*

可以用链表模拟，不过超时了。。。所以也不太知道模拟写的对不对，样例倒是通过了。

数学方法，$n$ 个数字，不断删除 $m$，将最后剩下的数字记为 $f(n, m)$，n 个数字中第一个被删除的应该是 $(m - 1) \mod n$，记为 $k$。

经过第一次删除后，从 $k + 1$ 开始计数，因此原来的位置被映射为：

原下标 $y$，映射后下标 $x$，可得到 $x \equiv (y - k - 1) \mod n \Rightarrow y \equiv (x + k + 1) \mod n$。

$n - 1$ 个数字，删除第 $m$ 个数字，剩下的是 $f(n - 1, m)$。将其还原回原始数字即 $(f(n - 1, m) + k + 1) \mod n$，也就是 $f(n, m)$ 。

由此得到递推公式：

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;
    }
};