题目

这道题是约瑟夫环可以用链表暴力删除，但是复杂度较高，是$O(mn)$

1. 数学递推公式法

题解中大部分都是对这个递推公式的讲解，我的个人理解如下

  1. 首先最后一次该数的pos肯定为0
  2. 递推前一次，由于每次是在当前位置往后推m个数，那么上一次的pos为m+pos
  3. 但是数组的长度是有限的，那么m+pos可能超过了当前数组的长度
    那么需要对这个数组进行取余，其中i就是当前数组的长度，从i开始一直到n，最后就得出如下的递推公式

核心就是一个数学递推公式：

  • 时间复杂度$O(n)$
  • 空间复杂度$O(1)$
class Solution {//约瑟夫环，数学递推公式法
public:
    int lastRemaining(int n, int m) {
        int pos = 0;//最后一个数的位置
        //从数组长度为2开始，一直到n
        for(int i = 2; i <= n; ++i){
            //递推公式
            pos = (pos + m) % i;
        }
        return pos;
    }
};