剑指offer 70- 圆圈中最后剩下的数字

0,1,…,n−1 这 n 个数字 (n>0) 排成一个圆圈，从数字 0 开始每次从这个圆圈里删除第 m个数字。

求出这个圆圈里剩下的最后一个数字。
样例

输入：n=5 , m=3

输出：3

分析：
算法一：约瑟夫环问题
直接暴力
时间复杂度

class Solution {
public:
    int lastRemaining(int n, int m){
        vector<int> nums;
        for (int i = 0; i < n; ++i) nums.push_back(i);
        
        auto it = nums.begin();
        int k = m - 1;
        while (nums.size() > 1){
            while (k--){
                it++;
                if (it == nums.end()) it = nums.begin();
            }
            it = nums.erase(it);//删除第m个元素
            if (it == nums.end()) it = nums.begin();
            k = m - 1;
        }
        return nums.front();
    }
};

算法二：
时间复杂度：

首先寻找递推公式
首先定义最初的n个数字中最后剩下的数字是关于n和m的方程为

第个数删掉，即删掉，然后剩下

对这些数重新编号





寻找映射关系：
即 =

递归写法：

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

递推写法：

class Solution {
public:
    int lastRemaining(int n, int m){
        // if(n==1) return 0;
        // return (lastRemaining(n-1,m)+m)%n;
        
        if (n == 1) return 0;
        vector<int> f(n + 1);
        f[1] = 0;
        for(int i = 2; i <= n; i ++){
            f[i] = (f[i - 1] + m) % i; //核心递推关系式
        }
        return f[n];
        
    }
};