题解 | #孩子们的游戏(圆圈中最后剩下的数)#

经典约瑟夫环问题。
这里需要掌握一个约瑟夫环的递推公式，f(n)=(f(n-1)+m)mod(n)。其中f(n)为在n个人中最后剩下的人，m为每次选出的人与第一个人的间隔。即若第一个人为0号，报到m-1的人出局。
该公式也比较容易理解，每次n个人中的第m个人出局，剩下的n-1个人组成新的约瑟夫环。这个新的约瑟夫环中的第一个人即是上一个约瑟夫环中的第m+1个人。同时，新约瑟夫环中最后剩下的人与旧约瑟夫环中最后剩下的人是同一个人。那么只要得到新约瑟夫环中最后剩下的人的编号，即能推出旧约瑟夫环中最后剩下的人的编号。其递推公式就是上面给出的公式。
利用上面的公式，可以递归求解该问题，当只剩下一个人，即n=1时，其编号必然为0，他就是最后剩下的人。

这种做法用到单层递归，时间复杂度为O(n)。由于递归需要使用到递归栈，空间复杂度为O(n)。而题目要求是时间复杂度为O(n)，空间复杂度为O(1)，递归的做法不能满足题目要求，说明题目想让我们使用迭代的方式来解决问题。

class Solution {
public:
    int LastRemaining_Solution(int n, int m) {
        if(n == 1){
            return 0;
        }
        return (LastRemaining_Solution(n - 1, m) + m) % n;
    }
};

迭代法。根据上面递归的写法很容易改写成迭代。
递归是从第n项开始，推到第一项的结果，在从第一项往回一项一项代入，最终得到第n项的结果。而迭代则是直接从第一项开始，一步一步推出第n项。

这种做法时间复杂度与递归相同，都为O(n)。由于其未使用递归栈，故空间复杂度更优，为O(1)。

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