题目链接
LeetCode 面试题62. 圆圈中最后剩下的数字[1]
题目描述
示例1
输入： n = 5, m = 3 输出 ：3
示例2
输入： n = 10, m = 17 输出： 2
说明：
题解
循环链表
递推法
对于本题这个方法已经够用了，但是如果 非常大，比如 ，但是 不是很大，比如 ，那么这时候这种方法就会超时了。具体的题目请自行百度 HDU 3089 。
递推法加速
数学法
这个方法在我之前的文章中已经讲过了：
具体数学-第8课（取整进阶）韦阳的博客：具体数学-第8课（取整进阶）[2]知乎专栏：具体数学-第8课（取整进阶）[3]知乎高赞回答也整理过了一遍：世界上有哪些代码量很少，但很牛逼很经典的算法或项目案例？[4]
大致思想也是重新编号，做编号映射，但是和上面递推法不同的是复杂度降到了对数级别。
这里就不详细讲了，大家可以去看上面的文章，这里直接给出伪代码：
D=1whileD<= (m-1)n: D=kans=mn+1-D
代码
递推法（c++）
classSolution { public: intlastRemaining(intn, intm) { intlast=0; for (inti=2; i<=n; ++i) { (last+=m) %=i; } returnlast; } };
递推法加速（c++）
classSolution { public: intlastRemaining(intn, intm) { if (m==1) returnn-1; intlast=0, t=1; for (inti=2; i<=n; i+=t) { t= (i-last+m-3) / (m-1); if (i+t-1>n) { last+= (n-i+1)*m; break; } (last+=t*m) %= (i+t-1); } returnlast; } };
数学法（c++）
classSolution { public: intlastRemaining(intn, intm) { longD=1, end= (long)n*(m-1); while (D<=end) { D= (m*D+m-2) / (m-1); } return (long)n*m-D; } };
参考资料
[1]
LeetCode 面试题62. 圆圈中最后剩下的数字: https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/
[2]
韦阳的博客：具体数学-第8课（取整进阶）: https://godweiyang.com/2018/04/16/concrete-math-8/
[3]
知乎专栏：具体数学-第8课（取整进阶）: https://zhuanlan.zhihu.com/p/35820332
[4]
世界上有哪些代码量很少，但很牛逼很经典的算法或项目案例？: https://www.zhihu.com/question/358255792/answer/974983270
作者简介：godweiyang，知乎同名，华东师范大学计算机系硕士在读，方向自然语言处理与深度学习。喜欢与人分享技术与知识，期待与你的进一步交流~
