注：

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

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

示例 1：
输入: n = 5, m = 3
输出: 3
示例 2：
输入: n = 10, m = 17
输出: 2

限制：
1 <= n <= 10^5
1 <= m <= 10^6

题解：
解题思路
最终剩下一个人时的安全位置肯定为0，反推安全位置在人数为n时的编号
人数为1： 0
人数为2： (0+m) % 2
人数为3： ((0+m) % 2 + m) % 3
人数为4： (((0+m) % 2 + m) % 3 + m) % 4
…
迭代推理到n就可以得出答案

方法一 递归
复杂度分析
时间复杂度：O(n)，需要求解的函数值有 n 个。
空间复杂度：O(n)，函数的递归深度为 n，需要使用 O(n) 的栈空间。

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

        return f(n,m);
    }
};

在这里插入代码片

方法二 迭代
复杂度分析
时间复杂度：O(n)，需要求解的函数值有 n 个。
空间复杂度：O(1)，只使用常数个变量。

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

在这里插入代码片

方法三 暴力法(超时)
复杂度分析
时间复杂度：O(m*n)
空间复杂度：O(n)

class Solution {
public:
    int lastRemaining(int n, int m) {
        vector<int> nums(n);
        for(int i=0;i<n;i++){
            nums[i]=i;
        }
        vector<int>::iterator it=nums.begin();
        while(nums.size()!=1){
            int t=m;
            while(t!=1){
                if((it+1)!=nums.end()){
                    it++;
                }
                else{
                    it=nums.begin();
                }
                t--;
            }
            vector<int>::iterator temp=nums.erase(it);
            if(temp==nums.end()){
                it=nums.begin();
            }
            else{
                it=temp;
            }
            
        }
        return *nums.begin();
    }
};