一、题目描述
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；
如果圆圈中有两个数字，那么所求数字的下标一定是0+m，如果超出了长度2，那就再%2；
如果圆圈中有三个数字，那么所求数字的下标一定是(0+m)%2 +m，如果超出了长度3，那就再%3
……
已经可以看出了，当有n个数字的时候，所求数字f(n)为：
f(n) = (f(n-1) + m) % i
三、Java代码实现
class Solution {
public int lastRemaining(int n, int m) {
int f = 0;
for(int i=2; i<=n; i++) {
f = (f+m)%i;
}
return f;
}
}四、时空复杂度分析
时间复杂度：O(N)
空间复杂度：O(1)
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/124977.html
