CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
## 题目
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof
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
求解
这是数学中著名的约瑟夫环问题。由于数据量给了限制，所以不方便使用模拟方法来求解，只能找一种时间复杂度为 O(n) 的算法来求解。 思路是递归。注意到当数是 n 个的时候，删除一个就变成 n-1 了，具有潜在的递归求解的思路。我们假设 f(n,m) 表示从 0 开始每次数 m 个数到最后得到的数，或者换句话说 f(n,m) 表示最后得到的数偏移起始位置多少个位置。开始时，删除的数显然是 n%m, 删除完之后就是 n-1 个数了。假如我们知道 f(n-1,m) 的值，即最后的数离起始位置差 x = f(n-1,m) 个数，那么 f(n,m) 最后删的数离起始位置(即 0)为： n%m + f(n-1,m)这么多，对应的数为 (n%m + f(n-1,m))%m。 而起始 n = 1时，显然 f(1,m) = 0, 所以代码就很简单了：
class Solution {
public:
int lastRemaining(int n, int m) {
if(n == 1) return 0;
return (lastRemaining(n-1,m) + m )%n;
}
};