本文主要是介绍23. 圆圈中最后剩下的数字，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、题目
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^2）
可以分析下纯暴力的做法，每次找到删除的那个数字，需要 O(m)的时间复杂度，然后删除了 n-1次。但实际上我们可以直接找到下一个要删除的位置的！
假设当前删除的位置是 idx，下一个删除的数字的位置是 idx +m 。但是，由于把当前位置的数字删除了，后面的数字会前移一位，所以实际的下一个位置是 idx +m−1。由于数到末尾会从头继续数，所以最后取模一下，就是 (idx + m - 1) mod n。
class Solution {public int lastRemaining(int n, int m) {ArrayList<Integer> list = new ArrayList<>(n);for(int i=0;i<n;i++){list.add(i);}int curm = 0; //记录要删除数字的下标（从0开始）while(n>1){// 删除第m个数字curm = (curm+m-1)%n;list.remove(curm);// 删除后的长度n--;}return list.get(0);}
}方法二：数学方法（O（n））
class Solution {public int lastRemaining(int n, int m) {int ans = 0;// 最后一轮只剩2个人。因此从2开始反推for(int i=2;i<=n;i++){ans = (ans+m) % i;}return ans;}
}
这篇关于23. 圆圈中最后剩下的数字的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
