剑指Offer_#62_圆圈中最后剩下的数字
Contents
题目
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思路分析
方法1：模拟法
按照题目意思，模拟题目描述的这个过程，一定可以得到答案，这就是模拟法。必须使用ArrayList来模拟"数字组成的圆圈"，才可以通过；如果使用LinkedList来模拟，时间超出限制。
算法流程
- 把0~n-1的数字添加到
ArrayList数据结构中。 - 按照题目规则，模拟删除节点的过程。
- 重点在于计算删除节点的索引，公式是
idx = (idx + m - 1) % n; - 解释：上一次删除的位置是
idx,下一次应该是idx + m,由于删除掉一个了，所有节点索引都减1，所以是idx + m - 1,又因为是环形的，所以走到结尾后还会重新开始向前走，所以对n求余。
- 重点在于计算删除节点的索引，公式是
- 返回最后剩下的一个数字。
方法2：数学公式法
这个问题其实是一个经典的数学问题，叫做"约瑟夫环"问题，可以通过一个递推关系式来计算幸存者的位置。数学公式法特点是公式推导过程比较难理解，但是一旦推导出公式，编码变得非常简单，且代码运行效率很高。
以下引用了一张题解中的图，这张图片清晰地展示了递推过程。
- 图中画了2个数组，是为了体现环形的特点，走到最后重新开始。
- 图中红色的数字是每一轮删除掉的数字。
- 绿色的线是每一轮中开头数字的变化情况。可以看到，因为每一次删除数字之后，从删除数字的下一个开始重新计算，所以开头数字每次会向前移动
m位 - 橙色的线是每一轮中幸存数字3的变化情况。幸存数字与开头数字一样，每轮向前移动
m位。
以上描述的过程是从上到下的过程，从原数组里逐渐删除数字，最后仅剩一个幸存数字。
那么重点来了，我们如果从下往上看，可以发现一个倒推的规律，与上述规律是互逆的。
从上向下看，幸存数字3每次向前移动m位；从下往上看，规律就是，幸存数字3每次向后移动m位。
并且，我们还有一个条件，幸存数字最后的索引一定是0。
根据这两个条件，我们可以发现从下往上看，幸存数字的索引的变化规律。
即(当前index + m) % 上一轮剩余数字的个数。
递推公式如下：
- 第四轮：(0+3) % 2 = 1
- 第三轮：(1+3) % 3 = 1
- 第二轮：(1+3) % 4 = 0
- 第一轮：(0+3) % 5 = 3
最后，我们找到了幸存数字在原数组里边的索引是3，由于原数组是0~n-1有序数组，索引就等于索引位置上的元素，直接返回3。
总结一下， 首先我们按照题目规则，一步步推导，可以得到最后幸存的数字3。得到幸存数字之后，从下到上观察幸存数字索引的变化，我们可以发现一个倒推的规律，利用这个规律，可以计算出幸存数字在原数组里的索引。
解答
解答1：模拟法
class Solution {
public int lastRemaining(int n, int m) {
//用ArrayList可以通过，LinkedList不可以通过，因为ArrayList删除元素时会快些
List<Integer> list = new ArrayList<>();
//将0~n-1的数字添加到链表中
for(int i = 0;i <= n - 1;i++){
list.add(i);
}
int idx = 0;
//按照规则，模拟删除节点的过程
while(n > 1){
//这一次要删除的节点的索引
idx = (idx + m - 1) % n;
//删除idx处的节点
list.remove(idx);
//删除了一个节点之后，长度减1
n--;
}
//返回最后剩下的数字
return list.get(0);
}
}复杂度分析
时间复杂度：大概是O(n2),因为remove()的复杂度是O(n)
空间复杂度：O(n),借助一个ArrayList
解答2：数学公式法
class Solution {
public int lastRemaining(int n, int m) {
//数学法，思路难，编码简单
//幸存者在最后一轮必然索引是0
int ans = 0;
for(int i = 2;i <= n;i++){
ans = (ans + m) % i;
}
return ans;
}
}复杂度分析
时间复杂度：O(n)
空间复杂度：O(1)