第一次在每日一题里碰到“面试题62.圆圈中最后剩下的数字”我第一反应是拿链表硬模拟写完一提交数据一大就超时直接被教做人。这道题还有一个大家更熟悉的名字——约瑟夫环。它表面是个“一群人围成圈删人”的游戏实际上考的是规模缩减、递推关系和取模映射属于那种“看着简单、想完全想明白很难”的经典题。这篇文章想把这道题从题目含义、公式推导到三种写法的取舍、常见的翻车点完整拆一遍。不管你是刚刷题的新手还是准备面试想巩固基础的老手看完应该都能把这道题彻底吃透而不是只背一个f(n) (f(n-1) m) % n的公式。1. 题目拆解与解题方向判断1.1 题目到底在问什么先按题目说的来0、1、...、n-1 这 n 个数字排成一个圆圈从数字 0 开始每次从这个圆圈里删除第 m 个数字。删除后从被删除数字的下一个数字开始继续计数再次删除第 m 个数字。重复这个过程直到圆圈里只剩一个数字求这个最后剩下的数字。这里的“第 m 个”按题目默认的从 0 开始计数的方式等于从当前起点数 m 个位置。例如 n5、m3 时从 0 开始数0、1、2数到 2所以第一次删除 2。删除后剩下 0、1、3、4从 3 开始数3、4、0数到 0所以第二次删除 0。按这个规则继续最后会剩下 3。这个样例可以自己推一遍先留个印象后面验证公式还要靠它。题目给的约束通常是 n1m1。n1 的情况最简单圆圈里只有 0 一个数字不用删最后就剩 0。这个边界条件看着不起眼但它是递推公式的起点后面会反复用到。1.2 为什么“模拟删除”看着很美却走不通拿到这题第一直觉一定是用一个环形链表或者数组去模拟删除过程把 n 个数字放进去每次找到第 m 个删掉直到剩一个。这个思路完全正确但它毁在复杂度上。如果用数组模拟每删一个元素后面的元素都要往前移动单次删除是 O(n)总共删除 n-1 次整体是 O(n^2)。如果用链表模拟删除单个节点是 O(1)但每次都要从头数 m 步才能找到要删的节点整体是 O(nm)。题目里 n 和 m 一旦到 10^5 这个量级O(nm) 就是 10^10 次操作任何在线评测系统都会给你一个无情的超时。我第一次做这道题就栽在这里链表写完了本地测试 n10000 还挺快换到 n100000、m100000 就卡死了。所以这类“只问最后幸存者不问删除过程”的题一旦模拟复杂度不可接受就要立刻转向数学解法也就是下面要说的递推公式。2. 递推公式的完整推导2.1 删除一个人之后问题悄悄变小了假设现在有 n 个人编号 0 到 n-1从 0 开始报数报到第 m 个的人出局。第一次删除的人是谁从 0 数到 m-1所以删除的是编号 m-1这里默认 m 不大于 n如果 m 大于 n就取模但删除位置仍然是 (m-1) mod n为了推导先假设 m 在 n 以内。删除之后圆圈里还剩 n-1 个人下一个报数起点是编号 m。这时候有意思的事情发生了从编号 m 开始剩下的人依次是 m, m1, ..., n-1, 0, 1, ..., m-2。这个顺序已经不再是 0 到 n-1 的连续排列而是一个“被切了一刀”的环。但本质上这 n-1 个人仍然围成一个圆圈仍然要从某个起点开始每次删第 m 个问最后剩下谁。这就和原来的问题结构一模一样只是人数从 n 变成了 n-1编号体系变了一套。2.2 重新编号旧编号和新编号之间就差一个 m既然 n-1 个人的问题结构和原问题相同那我可以把“从 m 开始的那一圈人”重新编号让第一个报数的人原编号 m变成新编号 0第二个报数的人原编号 m1变成新编号 1依次类推。这个重新编号的映射关系是这样的新编号 k对应原编号 (k m) % n。举个例子n5、m3第一次删掉编号 2 后剩下的人按报数顺序是 3,4,0,1。重新编号后原 3 变新 0原 4 变新 1原 0 变新 2原 1 变新 3。反过来看原编号 (新编号 m) % n这里取模的 n 是“当前这一轮的人数”也就是删除前的总人数 n。因为 m 可能大于 n所以加完 m 之后要模 n 回到这个环的范围里来。2.3 从 n-1 的结果反推 n 的结果设 f(n, m) 表示 n 个人编号 0~n-1从 0 开始报数每次删除第 m 个人最后幸存者的编号。第一次删除后剩下 n-1 个人。这 n-1 个人从原编号 m 开始重新编号之后问题变成了“n-1 个人从新编号 0 开始报数每次删除第 m 个人”这正是 f(n-1, m) 的定义。所以最终幸存者在“重新编号”体系里的编号就是 f(n-1, m)。再用上一节的映射关系把这个新编号还原成原编号原编号 (f(n-1, m) m) % n。这就是核心递推式f(n, m) (f(n-1, m) m) % n边界条件是 f(1, m) 0因为只有一个人时幸存者只能是 0。这个推导的关键在于我根本不需要真的去删除元素只需要知道“删除一次之后问题缩小成了同样结构的小问题”然后用映射关系把答案从小问题搬回大问题。这种“规模缩减 结构不变”的思路比背公式重要得多很多同类题都靠它。2.4 拿 n5、m3 手工验算一遍空说无凭把 n5、m3 代入递推式一步步算f(1, 3) 0 f(2, 3) (f(1, 3) 3) % 2 (0 3) % 2 1 f(3, 3) (f(2, 3) 3) % 3 (1 3) % 3 1 f(4, 3) (f(3, 3) 3) % 4 (1 3) % 4 0 f(5, 3) (f(4, 3) 3) % 5 (0 3) % 5 3最终答案是 3和前面手工模拟的结果完全一致。我自己第一次推这个表的时候最大的感受是“原来每一步都是在复用上一步的结果”而不是真的去模拟删除过程。建议你也找个小例子比如 n6、m4亲手从 f(1) 推到 f(6)推完这个公式就再也忘不掉了。3. 三种代码实现的对比与选择3.1 暴力模拟只配在小数据里自娱自乐虽然不能作为标准答案但暴力模拟适合用来验证递推公式的正确性。比如用一个循环链表或者数组按题目意思一步步删我经常拿它当“对拍器”小数据下和递推结果比对。下面这段用 Python 的 list 模拟注意 list.pop(i) 本身是 O(n) 的所以整体是 O(n^2)def last_remaining_bruteforce(n, m): arr list(range(n)) idx 0 while len(arr) 1: idx (idx m - 1) % len(arr) arr.pop(idx) return arr[0]这段代码只能用来做正确性验证。面试的时候如果写这个面试官大概率会追问一句“你觉得这个复杂度能过吗”答不上来比不写还尴尬。3.2 递归写法直观但隐藏着栈溢出风险公式都推出来了递归是世界上最自然的写法public int lastRemaining(int n, int m) { if (n 1) { return 0; } return (lastRemaining(n - 1, m) m) % n; }代码只有三行逻辑和递推式一一对应可读性极好。但要注意这个递归深度是 n当 n 达到 100000 甚至更大的量级时很多语言的函数调用栈会直接爆掉。在 Java 里默认栈深度通常几千到几万层n 一大必然 StackOverflow。所以递归写法适合用来“讲清楚思路”不适合拿来当正式提交答案。如果面试官不限制语言和资源你用递归展示推导过程没问题但最好主动提一句“工程上我会用迭代写法避免栈溢出”。3.3 迭代写法面试标准答案一行循环搞定把递归改成迭代从 f(1) 开始一路推到 f(n)只需要一个循环public int lastRemaining(int n, int m) { int ans 0; for (int i 2; i n; i) { ans (ans m) % i; } return ans; }这里为什么循环从 i2 开始因为 f(1)0 已知循环里算的是 f(2)、f(3)、...、f(n)每一步的取模分母都是“当前人数 i”。这个细节好多人写错写成(ans m) % n原理上就是混淆了规模。迭代写法的复杂度是 O(n) 时间、O(1) 空间。在 n 不超过 10^7 左右的常规数据下这是最优解也是面试官最想看到的答案。代码里还可以加一行注释说明递推来源面试时一边写一边念推导过程观感会很好。4. 从这道题延伸出来的常见坑与细节4.1 取模优先级一个括号引发的血案在 Java 和 C 里取模运算符%的优先级和乘除同级高于加减。所以(ans m) % i如果漏写括号写成ans m % i实际含义就变成了ans (m % i)结果完全错误。例如 ans1, m3, i2 时正确结果是 (13)%20错误写法是 1(3%2)2。这个错误在 n 小时不容易发现数据稍微大一点立刻出错而且很难排查因为我一度以为是取模运算本身的问题找了好久才发现是少了个括号。另外有个小优化可以提一下如果 m 很大m % i不会影响结果因为 (ans m) % i 等价于 (ans (m % i)) % i。但注意 i 是变化的不能提前只取一次模必须每一轮按当前的 i 来。实际写的时候我通常不加这个优化因为一个取模运算的开销可以忽略加了反而影响可读性。4.2 int 溢出极端数据下最容易翻车再看这个表达式(ans m) % i。如果 n 和 m 都很大比如 n10^9、m10^9ans 和 m 相加可能超出 int 的范围Java 里会溢出成负数模出来的结果自然也是错的。解决办法很简单把中间结果提升到 longpublic int lastRemaining(int n, int m) { long ans 0; for (int i 2; i n; i) { ans (ans m) % i; } return (int) ans; }C 里用long long同理。Python 没有这个问题因为 Python 的 int 是任意精度的。这个溢出问题在经典约瑟夫环的题目里不太常见但换一个数据范围大的变体题就很容易踩提前养成用 long 的习惯总没错。4.3 递归、迭代、暴力模拟三者的选型对比我自己在面试和日常刷题中会按下面的标准选方案时间复杂度空间复杂度代码量适用场景暴力模拟O(n*m) 或 O(n^2)O(n)较短小数据验证结果递归公式O(n)O(n) 栈空间最短展示推导思路迭代公式O(n)O(1)很短正式答案首选如果是笔试场景直接写迭代公式稳且快。如果是面试场景先讲递归公式的推导再主动补充一句“为了避免栈溢出我可以改成迭代”这比只扔出迭代代码更能体现你对问题的理解。4.4 一个容易忽视的细节题目里 m 的计数方式不同题目对“第 m 个”的表述可能不同。有的题说“每次数到 m 的人出列”这时候删除的是从当前位置数第 m 个人也就是代码里的(idx m - 1) % len如果题目改成“每次报到 m-1 的人出列”或者“从 1 开始报数”公式里的m就要相应调整。面试题62的做法是从 0 开始每次删除第 m 个数字。但在变体题里如果是从 1 开始编号、从 1 开始报数答案往往还要换算。刷题时第一个动作一定是确认编号起点和计数方式这个比写代码重要一百倍。5. 从这道题延伸出去的变体与复盘方法5.1 变体一要求输出完整的删除顺序怎么办如果题目从“求最后幸存者”改成“输出所有人被删除的顺序”递推公式就帮不上忙了因为公式只保留最终幸存者中间过程全部被压缩掉了。这时候老老实实模拟是唯一直观的思路但可以用平衡树来优化。用有序集合维护当前存活的人每次通过树上的二分找到第 k 个存活者并删除单次删除 O(log n)整体 O(n log n)。在 n 达到 10^5 量级时这个方案是可行的而且代码不算太复杂。如果直接用数组删除复杂度 O(n^2)只能处理 n 在几千以内的小数据。5.2 变体二m 远大于 n或者 n 特别大当 m 远大于 n 时递推公式依然成立因为每一步的% i会自动把 m 缩到当前人数的范围内所以仍然是 O(n) 时间。但如果 n 特别大比如 n10^12、m2普通的 O(n) 递推也跑不动了这时候需要用到更高级的数学优化比如快速跳过一段连续删除过程这类技巧已经超出这道面试题的讨论范围了。面试阶段只需要掌握 O(n) 的迭代公式就足够。遇到大数据范围的追问可以坦率地指出“这道题最优解就是 O(n)如果 n 超大规模需要数学加速”面试官通常不会在这个点上刁难。5.3 每日一题的正确刷法把一道题榨干这道题让我重新反思了刷每日一题的方法。很多人打开题解看到公式复制提交完事。但这样刷一百道题也留不下多少印象。我现在的做法是第一先花五到十分钟独立思考哪怕想到的只有暴力模拟也要把暴力代码写出来因为它是后面验证正确性的参照物。第二实在想不出来再去看题解看的时候重点看推导过程而不是只看代码。第三合上题解自己在纸上把 f(1) 到 f(n) 推一遍就像上面 2.4 节那样。第四第二天用另一种语言重新默写一遍巩固肌肉记忆。这套流程看着慢但对这道题非常有效。因为约瑟夫环的难点不在代码而在那层“重新编号”的映射窗户纸捅破了之后同类问题比如猴子选大王、报数出圈都能套同一个思路。最后再分享一点个人体会我第一次做这题的时候也是先写链表模拟被超时打脸之后才开始研究递推。当时卡在“为什么删除一个人之后重新编号的映射是加 m 再取模”这个点上花了整整一下午画图才把这层关系理顺。现在回头看这个下午很值因为从那以后凡是不需要输出删除过程的环形删除问题我都能条件反射地想到规模缩减递推。如果你现在也是靠背公式做这道题我真心建议你花二十分钟找一个 n6、m4 的样例从头开始手算一遍递推表。算完你会发现这个公式不再是天上掉下来的魔法而是一个顺理成章的结果。以后再遇到约瑟夫环的变体你就能自己推公式了而不是翻题解。