LeetCode 剑指 Offer 62. 圆圈中最后剩下的数字
题目描述
题意分析
编号
0到n - 1按顺序围成一个圆圈，从编号0开始报数，把当前起点算作第1个。每次数到第m个就删除它，再从被删位置的下一个人重新从1开始报数，直到只剩一个。返回最后留下的原始编号，不是最后一轮重新编号后的下标。人数会逐渐减少，报数超过一圈时继续绕圈；只求幸存者，不要求输出删除顺序。
解法：约瑟夫环递推
核心思路
[!blue]
如果真的维护圆圈并逐次删除，每轮都需要寻找被删位置。只求最后幸存者时，可以反过来研究：少一个人的圆圈已经知道答案，怎样把它映射回当前圆圈？
设
f(size)表示有size个人、从编号0开始报数时，最终留下的编号。第一次删除的是(m - 1) % size，所以下一轮起点是m % size。删除后剩余size - 1人，从新起点沿圆圈依次重新编号为0到size - 2，报数规则完全不变，因此新编号下的答案就是f(size - 1)。把新编号
x映射回删除前的编号，需要从下一轮起点向前走x个位置，即(x + m) % size。被删位置紧挨在这个起点之前，剩余size - 1个位置的映射会自然跳过它。因此递推式为f(size) = (f(size - 1) + m) % size。只有一个人时，无论每次数多少，幸存编号都是
0，所以从ans = 0开始，依次扩大人数。每一轮的ans都表示当前规模重新从零编号的答案；直到规模恢复为n，它才是题目所求的原始编号。加的是下一轮起点的偏移
m，不是被删位置的偏移m - 1。每次取模使用当前人数size，因此m大于人数时也能正确处理绕圈。
解题步骤
- 初始化
ans = 0，表示一人圆圈的幸存编号。- 让
size从2增加到n，每轮执行ans = (ans + m) % size。- 返回
ans。当n = 1时循环不执行，直接得到唯一编号0。
代码实现
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)$，只保留上一规模的答案，无须保存圆圈或递归栈。
关键点总结
[!green]
- 递推利用的是删除后规则不变，但需要把下一轮起点重新编号为零。
(m - 1) % size是被删位置，m % size才是新起点；还原编号要使用新起点。- 从小规模逐步映射到大规模，每次的答案含义和模数都对应当前人数。
易错点总结
[!yellow]
- 写成
ans + m - 1，会把被删位置当作下一轮起点，造成整体偏移。- 从
n向1直接套同一公式，方向不对；该公式依赖已经求出的f(size - 1)。- 提前只执行一次
m %= n会丢失后续所需信息，因为每一轮应对不同的size取模。- 本题编号从
0开始，不应在返回时加一；只有改成从1开始编号的版本才需要转换。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 补充题 197. 约瑟夫环的幸存者 | 中等 | 都使用约瑟夫递推；本题从 0 编号，补充题从 1 编号。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！