LeetCode 补充题 197. 约瑟夫环的幸存者
题目描述
:::fold-green 相关原题
LeetCode 原题： ✅ 1823. 找出游戏的获胜者
本文的报数步长 m 对应力扣参数 k，并采用更大的输入范围。
:::
n个人编号为1到n，从编号1开始每数到第m人就将其移出圆圈，下一人重新从1计数。返回最后留下的编号。
示例 1：
输入：
n = 5, m = 3
输出：4
提示：
-
1 <= n, m <= 1000000。
题意分析
模拟逐个报数和删除会重复扫描圆圈。只求最后的幸存编号时，可以利用删除第一人后剩余圆圈与规模少一人的同类问题之间的位置映射，逐步恢复答案。
解法：零基递推后转换编号
核心思路
[!blue]
先统一用从 0 开始的编号。只有一个人时，幸存位置为 0；记
ans为少一人圆圈中的幸存位置。扩展到 size 人时，第一次删除的位置是
m-1，下一轮从原编号 m 重新编号为 0。因此小圆圈中的位置 ans，映射回大圆圈就是(ans+m) % size。从 size=2 递推到 n 即可，不需要真的删除数组元素。题目最终使用 1 到 n 的编号，所以只在返回时加一。比如 n=5、m=3，零基答案为 3，题目编号为 4；不能在每轮递推中重复加一。
解题步骤
- 令 ans=0，表示只有一个人时的零基幸存位置。
- 将圆圈规模 size 从 2 增加到 n，每次更新 ans=(ans+m)%size。
- 返回 ans+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 + 1;
}
}
func lastRemaining(n int, m int) int {
ans := 0
for size := 2; size <= n; size++ {
ans = (ans + m) % size
}
return ans + 1
}
复杂度分析
- 时间复杂度：$O(n)$。
- 空间复杂度：额外空间 $O(1)$。
关键点总结
[!green]
递推仍使用从零开始的编号，每扩大一圈加上报数步长并取模，最终结果加一转换为题目编号。
易错点总结
[!yellow]
- 递推过程中始终使用零基位置，只在返回时加一。
- 每一步对当前规模 size 取模，不是始终对 n 取模。
- n=1 时无需进入循环，直接得到编号 1。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 剑指 Offer 62. 圆圈中最后剩下的数字 | 简单 | 约瑟夫环递推相同；该题使用 0 到 n-1 编号，本题使用 1 到 n 编号，因此零基递推结果需要加一。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！