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

思路：

题目的主要信息：

从0到n-1（首尾相接）中每次去掉第m个数，下一次从去掉数的下一个开始，直到剩下最后一个数
返回的是最后一个数
有数为0的特殊情况

方法一：递归
具体做法：
n个数相后去掉第m个数，还剩下n-1个数，依然要继续去掉第m个数。由此，从(n,m)的问题变成了(n-1,m)的子问题，其中若是(n-1,m)的子问题返回的最后一个数是x，则(n,m)返回的结果就是 $(m+x)\%n$ ，其中边界是n==1的时候返回0.因此，用递归解决。
图片说明

class Solution {
public:
    int function(int n, int m) {
        if (n == 1)  
            return 0;
        int x = function(n - 1, m);//递归
        return (m + x) % n;  //返回最后删除的那个元素
    }
    int LastRemaining_Solution(int n, int m) {
        if(n == 0 || m == 0) //没有小朋友的情况
            return -1;
        return function(n, m);
    }
};

复杂度分析：

时间复杂度： $O(n)$ ，每个元素访问一次
空间复杂度： $O(n)$ ，递归栈最大深度

方法二：迭代
具体做法：
方法一的递归也可以用迭代来代替，每次记录并更新x即可。

class Solution {
public:
    int LastRemaining_Solution(int n, int m) {
        if(n == 0 || m == 0) //没有小朋友的情况
            return -1;
        int x = 0;
        for (int i = 2; i <= n; i++)
            x = (m + x) % i;//从小到大，更新x
        return x;
    }
};

复杂度分析：

时间复杂度： $O(n)$ ，一次遍历
空间复杂度： $O(1)$ ，常数个变量，无额外空间

方法三：链表模拟法
具体做法：
用list模拟链表，每次遍历m个结点便删除一个，到链表尾时指定到链表头以作循环。最后
当剩下一个结点时，就是最后的结果。

class Solution {
public:
    int LastRemaining_Solution(int n, int m) {
        if(n == 0 || m == 0) //没有小朋友的情况
            return -1;
        //数组模拟法
        list<int> set;
        for(int i = 0; i < n; i++)
            set.push_back(i);
        auto iter = set.begin();
        while(set.size() > 1){
            //循环找到第m个
            for(int j = 0; j < m - 1; j++){
                iter++;
                if(iter == set.end()) 
                    iter = set.begin();
            }
            //删除第m个，并判断删除的是否为最后一个，循环
            iter = set.erase(iter);
            if(iter==set.end()) 
                iter = set.begin();
        }
        return *set.begin();
    }
};

复杂度分析：

时间复杂度： $O(mn)$ ，相当于遍历n次，每次m个结点
空间复杂度： $O(n)$ ，list链表的空间