LeetCode 剑指 Offer 62. 圆圈中最后剩下的数字
目录
题目描述
题意分析
0, 1, ..., n-1这n个数字围成一个圈，从数字 0 开始，每次从当前位置起数m个数字，把数到的那个删掉，然后从被删数字的下一个位置继续数。要求返回最后剩下的那个数字。要点有三个。第一，返回的是数字本身，也就是它在最初圆圈里的编号，而不是它在某一轮里的位置，更不是删除的次数。第二，圆圈是首尾相接的，数到末尾要绕回开头，所以一切位置计算天然带取模。第三，每次删除之后，下一轮的起点固定是被删元素的后一个，这个规则让每一轮之间的关系是齐次的。
约束是
1 <= n <= 10^5、1 <= m <= 10^6。n到10^5这个量级本身不算大，但它排除了「一轮一轮真的走m步」的写法：那样总步数是 $O(nm)$，最坏到10^11。同时n只有一维，说明答案应该只跟规模n和步长m有关，不需要维护整个圆圈的形态，这是一个很强的信号。边界情况：
n = 1时圈里只有数字 0，不需要删除，直接就是答案；m可以远大于n，绕好几圈才删掉一个，所以任何一步都必须先取模再用。
解法：约瑟夫环递推
核心思路
问题关键：模拟删除需要维护整个圆圈，而题目只问最后一个编号。删除第一个人后，剩余
i-1个人仍是同一个问题，只是编号起点发生了旋转。状态与推导：令
f(i)表示i个人按0..i-1编号时的最终幸存者。第一轮删掉(m-1) % i，下一轮从m % i开始，并把这个位置重新编号为0。若幸存者在新编号中是x=f(i-1)，映射回旧编号需要整体右移m位：
f(i) = (f(i-1) + m) % i，且f(1) = 0。为什么选递推：公式只依赖前一个规模，用一个变量从
2推到n即可；无需链表、删除操作或递归栈。不变量与正确性：循环处理完
size后，ans始终等于f(size)。初始ans=0=f(1)；若上一轮成立，按编号映射(x+m)%size得到的正是当前规模幸存者，所以归纳成立，循环结束时得到f(n)。
解题步骤
- 令
ans = 0，表示规模为1时唯一的幸存者是编号0。- 让
size从2增长到n，每次执行ans = (ans + m) % size。- 循环结束后返回
ans。口述样例：
n=5, m=3时，f(1..5)依次为0,1,1,0,3，因此最后剩下编号3。边界检查：
n=1时循环不执行，直接返回0；m远大于当前人数时，取模会自动处理绕圈；m=1时结果依次右移一位，最终为n-1。
代码实现
class Solution {
public int lastRemaining(int n, int m) {
int ans = 0;
for (int size = 2; size <= n; size++) {
ans = (ans + m) % size;
}
return ans;
}
}
func lastRemaining(n int, m int) int {
ans := 0
for size := 2; size <= n; size++ {
ans = (ans + m) % size
}
return ans
}
复杂度分析
- 时间复杂度：$O(n)$，共进行
n-1次常数时间递推。- 空间复杂度：$O(1)$，只滚动保存当前答案。
关键点总结
- 公式的核心不是背诵，而是理解「删除后以谁为新 0 号」。
(m-1)%i是被删除的位置，m%i才是下一轮起点，因此还原编号要加m。- 递推方向只能从小规模推到大规模；每轮模数都不同。
易错点总结
- 写成
ans + m - 1：混淆被删除位置与下一轮起点；n=5,m=3会得到2而不是3。- 从
n向1递推：公式表达的是小规模答案如何映射回大规模，不能直接反用。- 提前固定执行
m %= n：每一轮的模数是当前size，不能只按初始人数取模。- 用数组或链表真实删除：维护了不需要的状态，最坏达到 $O(n^2)$ 或 $O(nm)$。
- 写成递归：
n=10^5时可能栈溢出，循环没有额外复杂度。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 292. Nim 游戏 | 简单 | 从必败态倒推规律，结论是对 4 取模，无需递推数组 |
| 390. 消除游戏 | 中等 | 同样是「删一轮变子问题」，但方向左右交替，需维护首元素与步长 |