示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载本篇技术指南以 doocs/leetcode 仓库中 面试题 62. 圆圈中最后剩下的数字 的官方题解为骨架完整讲解约瑟夫环Josephus Problem问题的数学推导、递归解法与迭代优化并给出仓库内 Python、Java、C、Go、JavaScript、C#、Swift 的对照实现。读完本文你将掌握 $f(n,m)(mf(n-1,m))\bmod n$ 这一核心递推式的推导过程、时间复杂度与空间复杂度分析并能将同一思路迁移到 1823. 找出游戏的获胜者 等同类环形淘汰问题。题目概述0,1,···,n-1 这 n 个数字排成一个圆圈从数字 0 开始每次从这个圆圈里删除第 m 个数字删除后从下一个数字开始计数。求出这个圆圈里剩下的最后一个数字。例如0、1、2、3、4 这 5 个数字组成一个圆圈从数字 0 开始每次删除第 3 个数字则删除的前 4 个数字依次是 2、0、4、1因此最后剩下的数字是 3。删除过程如下第 1 轮从 0 开始数第 3 个数字是 2删除 2从 3 继续计数第 2 轮从 3 开始数第 3 个数字是 0删除 0从 1 继续计数第 3 轮从 1 开始数第 3 个数字是 4删除 4从 1 继续计数第 4 轮从 1 开始数第 3 个数字是 1删除 1剩下 3。示例 1输入: n 5, m 3 输出: 3示例 2输入: n 10, m 17 输出: 2限制1 n 10^51 m 10^6从数据范围可以看出n 最大可达 $10^5$若采用链表或数组模拟每轮删除一个数字虽然直观但每次定位第 m 个数字需要 $O(n)$ 的遍历整体复杂度达到 $O(n^2)$在 n 较大时无法通过而 m 可远大于 n如示例 2 中 m17、n10此时取模运算在推导中扮演关键角色。这正是需要数学递推解法的原因。核心递推从删除一个数字后的编号重映射说起设 $f(n, m)$ 表示从 n 个数中每次删除第 m 个最后剩下的是第几个数字编号从 0 开始。第一次我们删除了第 m 个数字编号为 $(m-1) \bmod n$剩下的 n-1 个数重新组成一个圆圈并且下一次计数从被删除数字的下一个数字开始。此时这 n-1 个数的相对编号被重新组织为 $0, 1, \cdots, n-2$。设 $x f(n - 1, m)$它表示从重新编号后的 n-1 个数中每次删除第 m 个最后剩下的是这 n-1 个数中的第几个相对编号。那么 $f(n, m)$ 应该如何从 x 还原关键在于建立相对编号与原始编号之间的映射关系原始编号为 $(m \bmod n)$ 的数字在删除第 m 个数字后成为新一轮计数起点其相对编号为 0因此原始编号 $ (m \bmod n \text{相对编号}) \bmod n$。于是有核心递推式$$ f(n, m) (m \bmod n x) \bmod n (m f(n-1, m)) \bmod n $$边界条件为$$ f(1, m) 0 $$当 n 为 1 时圆圈中只剩数字 0最后留下的数字序号一定为 0。为什么可以写成 $(m x) \bmod n$由于 $x f(n-1, m) \in [0, n-2]$而 $(m \bmod n x)$ 可能超过 n因此需要再次对 n 取模。而 $(m \bmod n x) \bmod n$ 与 $(m x) \bmod n$ 在数学上是等价的模运算的结合律所以仓库题解中直接写成 $(m x) \bmod n$ 即可无需先对 m 取模。小规模验证以 n 5、m 3 为例逐步递推$f(1, 3) 0$$f(2, 3) (3 0) \bmod 2 1$$f(3, 3) (3 1) \bmod 3 1$$f(4, 3) (3 1) \bmod 4 0$$f(5, 3) (3 0) \bmod 5 3$最终得到 $f(5, 3) 3$与题目示例输出一致验证了递推式的正确性。方法一数学 递归根据上述递推式可以直接写出递归解法。递归求解即可也可以改成迭代。各语言实现Python3见 Solution.pyclass Solution: def lastRemaining(self, n: int, m: int) - int: def f(n, m): if n 1: return 0 x f(n - 1, m) return (m x) % n return f(n, m)Java见 Solution.javaclass Solution { public int lastRemaining(int n, int m) { return f(n, m); } private int f(int n, int m) { if (n 1) { return 0; } int x f(n - 1, m); return (m x) % n; } }C见 Solution.cppclass Solution { public: int lastRemaining(int n, int m) { return f(n, m); } int f(int n, int m) { if (n 1) { return 0; } int x f(n - 1, m); return (m x) % n; } };Go见 Solution.gofunc lastRemaining(n int, m int) int { var f func(n, m int) int f func(n, m int) int { if n 1 { return 0 } x : f(n-1, m) return (m x) % n } return f(n, m) }Swift见 Solution.swiftclass Solution { func lastRemaining(_ n: Int, _ m: Int) - Int { return f(n, m) } private func f(_ n: Int, _ m: Int) - Int { if n 1 { return 0 } let x f(n - 1, m) return (m x) % n } }复杂度分析时间复杂度$O(n)$每次递归只做一次取模运算共递归 n 层空间复杂度$O(n)$递归调用栈深度为 n。当 n 达到 $10^5$ 时部分语言的默认栈深度可能告警因此实际工程中更推荐方法二的迭代写法见下文。方法二数学 迭代自底向上递归深度为 n。同一递推式可以自底向上从 2 滚到 n只需要一个变量空间降为常数 $O(1)$彻底规避递归栈溢出风险。递推的迭代展开令 f 从 0 开始对应 $f(1, m)0$随后对 i 从 2 到 n 依次执行 $f (f m) \bmod i$。各语言实现Python3见 Solution2.pyclass Solution: def lastRemaining(self, n: int, m: int) - int: f 0 for i in range(2, n 1): f (f m) % i return fJava见 Solution2.javaclass Solution { public int lastRemaining(int n, int m) { int f 0; for (int i 2; i n; i) { f (f m) % i; } return f; } }C见 Solution2.cppclass Solution { public: int lastRemaining(int n, int m) { int f 0; for (int i 2; i n; i) { f (f m) % i; } return f; } };Go见 Solution2.gofunc lastRemaining(n int, m int) int { f : 0 for i : 2; i n; i { f (f m) % i } return f }JavaScript见 Solution.js 中的迭代版本/** * param {number} n * param {number} m * return {number} */ var lastRemaining function (n, m) { let f 0; for (let i 2; i n; i) { f (f m) % i; } return f; };C#见 Solution.cspublic class Solution { public int LastRemaining(int n, int m) { int f 0; for (int i 2; i n 1; i) { f (f m) % i; } return f; } }复杂度分析时间复杂度$O(n)$空间复杂度$O(1)$仅使用一个整型变量 f。这也是应对题目限制1 n 10^5的最优写法既不会像模拟法那样退化到 $O(n^2)$也不会像递归法那样产生 $O(n)$ 的调用栈。易错点与边界情况编号从 0 开始还是从 1 开始本题目编号为 0, 1, ···, n-1因此边界 $f(1, m)0$而 1823. 找出游戏的获胜者 中编号从 1 开始其递推式对应为 $ans (k f(n-1, k)) \bmod n$当结果为 0 时需要映射回 n见 Solution.py 等实现。两题递推本质相同差别仅在编号基线与取模结果的归一化处理。m 大于 n 的情况m 可达 $10^6$ 而 n 最大 $10^5$此时 m 可能远大于 n。递推式中 $(f m) \bmod i$ 的取模操作天然处理了这种情况无需额外对 m 取模预处理这也是递推解法的优势之一。递归爆栈方法一在最坏情况下递归深度等于 n$10^5$部分语言默认栈空间不足。若环境对递归深度有限制应优先使用方法二的迭代实现。int 溢出$(f m)$ 中 f 小于当前 i即小于 n最大 $10^5$m 最大 $10^6$两者之和不超过约 $1.1 \times 10^6$在 32 位 int 范围内完全安全各语言实现均无需使用长整型。同类问题扩展LeetCode 1823「找出游戏的获胜者」在 doocs/leetcode 仓库的 solution/1800-1899/1823.Find the Winner of the Circular Game/README.md 中收录了同一递推思路的变体n 名小伙伴围成一圈从编号 1 开始沿顺时针数 k 名小伙伴包含起始者最后被数到的人离开圈子求最终获胜者。该题与面试题 62 的差异在于编号从 1 而非 0 开始因此递推边界为 $f(1, k) 1$递推式为 $ans (k f(n-1, k)) \bmod n$当结果为 0 时代表编号 n需要显式归一化题目 n 仅到 500因此除了数学解法模拟法用数组 splice 删除在该数据范围内也能通过可以作为对照理解两种思路的适用边界。两题对比学习可以加深对编号重映射这一约瑟夫环核心思想的理解无论编号从几开始核心都是把 n 人问题的答案通过一轮删除后的相对编号递归或迭代地转化为 n-1 人问题的答案。小结面试题 62「圆圈中最后剩下的数字」是约瑟夫环问题的经典形式其最优解法建立在一条简洁的递推式之上$$ f(n, m) \begin{cases} 0, n 1 \ (m f(n-1, m)) \bmod n, n 1 \end{cases} $$方法一递归直接翻译递推式代码最直观时间复杂度 $O(n)$、空间复杂度 $O(n)$方法二迭代自底向上滚动计算时间复杂度 $O(n)$、空间复杂度 $O(1)$是应对 $n 10^5$ 数据范围的最优实现。在 doocs/leetcode 仓库中该题位于 lcof/面试题62. 圆圈中最后剩下的数字/ 目录包含 Python、Java、C、Go、JavaScript、C#、Swift 共 7 种语言的递归与迭代两套实现Solution 与 Solution2并可在 lcof/README.md 题解总表中检索到该题入口。掌握这条递推式及其推导过程后无论是面试手写还是应对环形淘汰类变体题如 1823都能快速给出线性时间、常数空间的优雅解法。赞分享示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载相关推荐CS-Notes 剑指 Offer 题解 62圆圈中最后剩下的数——约瑟夫环问题的递推公式与 O(1) 空间实现CS Notes 剑指 Offer 题解 62圆圈中最后剩下的数——约瑟夫环问题的递推公式与 O 1 空间实现 本篇基于 剑指 Offer 题解 62. 圆圈文档教程知识库剑指Offer No46「孩子们的游戏圆圈中最后剩下的数」约瑟夫环问题四种解法与递推公式详解剑指Offer No46「孩子们的游戏圆圈中最后剩下的数」约瑟夫环问题四种解法与递推公式详解 本文以 InterviewGuide 仓库中 46 剑指of文档教程知识库剑指 Offer 62 约瑟夫环最后剩下的数字从 O(nm) 模拟到 O(n) 动态规划LeetCode-Book剑指 Offer 62 约瑟夫环最后剩下的数字从 O nm 模拟到 O n 动态规划LeetCode Book 本篇围绕《剑指 Offer 62. 圆圈中示例工程教程教育上一篇VIC水文模型终极指南从配置陷阱到精准模拟的10个实战经验下一篇ReoGrid为企业级应用量身定制的.NET电子表格解决方案创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考