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

题解一：暴力法
解题思路：用数组模拟循环列表，从0开始喊到m个数后，就将其值置为-1。直到数组剩下最后一个数（非-1）。
样例如下：

复杂度分析：
时间复杂度：O(N^2)
空间复杂度：O(N)，申请一个数组标记每个小孩子是否退圈

class Solution {
public:
    int LastRemaining_Solution(int n, int m) {
        if (m == 0)return -1;
        vector<int> child(n + 1,0);//
        int k = 0,j=0;//k=出圈的小孩数,j=报数编号
        for (int i = 0;k!=n-1; i=(++i) % n) {//i=(++i) % n这里是一个特殊操作，使遍历自动再数组内循环。
            if (child[i] == 0) {
                j++;
                if (j == m) { j = 0; child[i] = 1; k++; }//此位置小孩退圈
            }
        }
        for (int i = 0; i < n; i++) {
            if (!child[i])return i;//找到最后的那个hai'zi
        }
        return -1;
    }
};

题解二： 约瑟夫问题递推公式
解题思路： 利用约瑟夫问题的递推公式 f(n,m) = ( f(n-1,m) +m)%n )
公式递推：
令f(n,m)表示最后一个人的下标。
1.假设有n个人，报数m， 从0 开始报数，易知出圈的人下标为 m-1。
2.m-1 出圈后，我们对剩余人重新编号 即 第m个人下标为0，第m+1 下标为1 ......以此编号。 那么重新编号之后，那么最后一个人的下标为f(n-1,m)
问题1： 在重新编号之后的f(n-1,m) 与 重新编号之前的f(n,m)有什么关系？
重新编号之前 m, m+1,m+2,....
重新编号之后 0 ，1 ，2，....
可知 (新编号+m)%n = 旧编号
3. f(n,m) = (f(n-1,m)+m) %n;
递归写法复杂度分析：
时间复杂度： O(N)
空间复杂度： O(N)

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

改写迭代法：

class Solution {
public:
    //约瑟夫
    int LastRemaining_Solution(int n, int m) {
        if(n<=0) return -1;
        int f = 0;
        for(int i  = 2;i!=n+1;i++)
        {
            f = (m+f) % i;
        }
        return f;
    }
};