题意整理:

去除题中的无关成分，实际上就是给出一个数组长度n，以及一个数字m,删除从起点开始的第m个数，最开始的起点为0，后面的起点为被删除元素的下一个元素。

实际上，理清题意后可以发现，本题即为约瑟夫环问题。最容易想到的思路就是使用数组模拟，但这涉及大量的数据搬运工作，非常耗时。一个优化就是使用链表表示数据进行模拟，这样可以省去数据搬运的时间，但时间复杂度仍为。但实际上，对约瑟夫环问题，进行一些观察很容易发现一个不需要模拟的更优的解题思路

方法一：数学 + 递归

核心思想：

可以对一个数列进行实际观察，这样更容易发现规律。

假设 表示 个人，指定的数为 时最后留下的序号。对 个人，会被删除的元素即为 编号为 的元素，删除后的序列长度为。可以尝试着先求出，此时两个队伍的开头元素并不相同，需要分析如何让它表示 。
假设对 ， 得到的答案的序号为 , 需要分析的即为在长度为 的序列中的序号。
由于第 个元素在这一轮被删除了， 是从被删除元素后开始数起的，所以 。
当时，有

核心代码：

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

复杂度分析：

时间复杂度：,递归次数与n成正比，每递归一次减小
空间复杂度：，递归深度为 , 所以使用的栈空间为

方法二：数学 + 迭代

核心思想：

可以将方法一的递归转换为迭代，同样是利用公式

核心代码：

class Solution {
public
    int LastRemaining_Solution(int n, int m) {
        if (n == 0) return -1;
        int ans = 0;
        for (int i = 2; i <= n; ++i) {
            //从f(2,m)计算到 f(n,m)
            ans = (ans + m) % i;
        }
        return ans;
    }
};

复杂度分析：

时间复杂度：,需要一个for循环，其次数为，故时间复杂度为
空间复杂度：，只用了常数个变量