约瑟夫问题升级版：从递推公式到动态步长与海量数据优化

约瑟夫问题升级版这个名字乍一听像是教科书里那道经典题的“加量不加价”版本但真正上手之后你会发现它根本不是一个题而是一整类问题的集合。约瑟夫问题本身大家都不陌生一群人围成一圈按固定步长报数报到的人出圈问最后剩下的人是哪一个。放在数据结构课上它通常被用来练循环链表放在算法题里它考察的是递推与编号映射而放到真实工程场景订单队列的淘汰策略、缓存扫描的幸存节点、甚至是多人对战游戏的出局判定底层都有它的影子。这篇文章就是想把这些被我实际踩过的、绕过弯路的约瑟夫问题升级版完整讲清楚从经典递推到动态步长、双向报数、海量数据加速三种升级变体最后附上可直接复现的代码和高频Bug排查清单。适合谁看正在准备算法面试的开发者、学数据结构卡在链表章节的学生、以及需要在业务里处理环形淘汰逻辑的工程师。内容尽量用“能直接抄作业”的方式组织所有推导都给出过程所有代码都标注了关键注释。1. 从经典到升级约瑟夫问题到底难在哪1.1 经典约瑟夫环的正确打开方式先对齐一下标准问题描述有 n 个人编号从 1 到 n围成一圈。从编号 1 的人开始报数报到 m 的人出圈然后从下一个人重新从 1 开始报数循环往复直到只剩一个人求这个人的编号。教科书喜欢用链表模拟构造一个循环链表每次走 m-1 步删除当前节点继续。这个思路非常直观写出来也没几行但它有一个天然的问题——你只是“模拟”了过程并不知道答案的规律。比如 n7、m3 时最后剩下的是 4n10、m2 时最后剩下的是 5。你很难靠肉眼总结出“幸存者跟 n、m 到底满足什么函数关系”。所以理解约瑟夫问题不能只停留在“会模拟”。我自己的体会是这道题真正有趣的不是链表删除而是两个视角的转换第一个视角叫“当前轮次”第二个视角叫“重新编号”。这两者一旦打通后面所有升级变体都会顺很多。1.2 模拟法为什么会被数据规模拖垮直接模拟的复杂度是 O(n×m)。n 是人数m 是步长。每淘汰一个人平均要走 m 步一共要淘汰 n-1 个人所以总步数约等于 n×m。当 n 和 m 都是 10^5 级别时这个数字直接来到 10^10本地跑一遍可能就要几十秒如果 m 是 10^9模拟法基本等于死路。有人可能会说那我用数组取模模拟呢数组模拟在删除时需要搬移大量元素单次删除就是 O(n)总复杂度反而变成 O(n²)比链表更慢。所以数据结构和算法得配套选不是“我用数组就一定快”。真正能扛住大规模数据的是数学递推解法。它把复杂度压到 O(n)空间 O(1)。这也是我理解的“约瑟夫问题升级版”第一层含义当数据规模变大时你必须有脱离模拟的抽象能力。1.3 升级版要解决的三类核心痛点我梳理了一下市面上常见的“约瑟夫问题升级版”基本逃不出三类痛点。第一类规模痛点。n 能到 10^7、10^8甚至更大m 也可能非常大。这时候循环链表肯定不行普通递推在 m 极大时虽然 O(n) 能跑但常数优化和跳步技巧就成了关键。第二类规则痛点。步长不再固定为常数 m而是一个会变的数组或者报数到一半方向反转从顺时针突然变成逆时针甚至出圈规则变成“报到质数出圈”“报到偶数的人决定下一轮方向”等花式规则。第三类工程痛点。约瑟夫问题不只是算法题它背后是“环形结构 计数淘汰 状态更新”这一套通用模型。缓存淘汰、任务调度、分布式节点选举都可能抽象成类似逻辑。工程场景里参数往往是动态的不能拿纸面公式硬套得设计可配置、可扩展的实现。所以这篇文章讲的不是某一道题的答案而是一套应对升级变体的“工具箱”。2. 核心升级递推公式推导与O(n)解法2.1 递推思路把“重新编号”用到极致递推解法的核心思想是剩 i 个人时的胜者位置可以由剩 i-1 个人时的胜者位置推导出来。我举一个具体的例子。假设 n7m3编号从 0 开始。先手动跑一遍完整过程第 1 轮0 1 2 3 4 5 6从 0 开始报数报到 2 的人出圈所以 2 出圈。剩下 0 1 3 4 5 6。 第 2 轮从 3 开始继续报数报到 5 的人出圈。剩下 0 1 3 4 6。 第 3 轮从 6 开始继续报数报到 1 的人出圈。剩下 0 3 4 6。 第 4 轮从 3 开始继续报数报到 6 的人出圈。剩下 0 3 4。 第 5 轮从 0 开始继续报数报到 3 的人出圈。剩下 0 4。 第 6 轮从 4 开始继续报数报到 0 的人出圈。剩下 4。所以 0-based 编号下最后幸存者是 4换成 1-based 编号就是 5。等等我故意在这里写了个容易踩坑的例子很多资料会说 n7、m3 的幸存者是 4但那是在 1-based 编号下也就是 1 到 7 编号时剩下 4 号。如果代码里用 0-based 编号最后要输出 ans1。现在看递推怎么来的。假设我们已经知道“剩 i-1 个人时胜者在当前环中的编号”是 f(i-1)现在要把这个结论“塞回”剩 i 个人的状态。剩 i 个人时第一轮会出圈的那个人编号是 (m-1) % i。他出圈后下一个人成为新一轮编号的“起点”。如果以这个起点重新编号那么新编号 0 对应原编号 m % i新编号 1 对应原编号 (m1) % i依此类推。反过来如果知道剩 i-1 个人时胜者在新编号下的位置 f(i-1)那么它在原 i 人环里的位置就是f(i) (f(i-1) m) % i这就是核心递推式。边界条件是 f(1) 0因为只剩一个人时胜者自然是唯一的 0 号。2.2 从推导到代码为什么总是差一个1用上面的公式算一遍 n7、m3 的完整递推表会非常直观if(i) 计算过程结果1f(1)02(03)%213(13)%314(13)%405(03)%536(33)%607(03)%73递推得到 0-based 编号是 3换算成 1-based 就是 4和手动模拟的 1-based 结果一致。代码写出来非常短def josephus(n: int, m: int) - int: # 0-based 递推最后 1 转成 1-based f 0 for i in range(2, n 1): f (f m) % i return f 1这个版本时间复杂度 O(n)空间 O(1)。理论上 n10^7、m 固定的情况它也能在可接受的时间内跑完。之所以很多人代码写出来“差一个 1”是因为推导时用 0-based但题目要求输出 1-based或者反过来。我的建议是全代码统一用 0-based 递推只在最终输出时 return f 1中间任何一步都不要动编号基准否则很容易乱。用生活类比解释一下这个递推。想象你是一个排队的人队伍会不断有人离开离开后就重新从下一个人开始编号。递推本质上是“我从第二轮开始一路往前倒推”——我不用关心每一轮谁走谁留我只需要知道“上一轮胜者在上一轮队伍里的位置”然后逆着规则把它挪回本轮队伍的位置。每增加一个人相当于把整个队伍的位置整体向后平移 m 个位置但受限于“绕圈”要用取模修正。这里有一个新手容易忽略的细节如果 m 非常大甚至大于 i公式里的 % i 会自动处理回绕所以不需要在代码里手动把 m 对 i 取模后再代入。直接把 fm 放在一起取模数学上等价。3. 三种常见升级变体与应对方案3.1 变体一步长动态变化怎么保证递推不出错第一种升级变体最常见步长不是固定值而是一个数组比如第 1 轮报数报到 3 出圈第 2 轮报到 5 出圈第 3 轮报到 2 出圈……这种场景在游戏里特别多比如每关淘汰人数规则不一样。如果继续用 O(n×m) 的模拟也能写但步长一变原来那个固定 m 的递推公式就得跟着改。正确的改法是设 k 为长度 n-1 的数组k[0] 表示第 1 轮剩 n 个人时的步长。递推时仍然从 i2 往上走但每一步用的步长不是同一个 k而是对应的那一轮def josephus_dynamic_k(n: int, k: list[int]) - int: # k[0] 是第一轮的步长k[n-2] 是最后一轮的步长 f 0 # 只剩 1 人时胜者是 0 for i in range(2, n 1): # 人数从 i-1 变到 i 时回退到第 n-i 轮0-based step k[n - i] f (f step) % i return f 1这里最容易踩的坑是下标。我实际调错过一次把 step 取成 k[i-2]结果小规模用例怎么都对不上。后来手动推了一遍才发现当 i 从 2 涨到 n 时对应的其实是“从最后一轮往第一轮回溯”所以要用 k[n-i] 而不是 k[i-2]。举个例子。n4k[2, 3, 1]表示第 1 轮走 2 步第 2 轮走 3 步第 3 轮走 1 步。手动模拟比较麻烦但用递推很快f(1)0 i2 时stepk[4-2]k[2]1f(01)%21 i3 时stepk[4-3]k[1]3f(13)%31 i4 时stepk[4-4]k[0]2f(12)%430-based 结果是 31-based 就是 4。如果和模拟结果对比应该是 4。这个下标规律值得你亲手验算一遍验证通过以后动态步长变体就不再神秘了。3.2 变体二双向报数与方向切换链表模拟的实战价值第二种升级变体更“花哨”报数到一半方向反转。比如规定“如果本轮回合出圈的人是偶数编号下一轮反向报数”或者“每隔 k 轮方向切换一次”。这种变体想用纯递推公式硬推不能说不可能但非常难而且每加一条规则递推式就要重新推导。相比之下用双向循环链表模拟反而更稳因为你只需要在指针移动方向上加一个标记变量每次方向反转时切换它即可。伪代码思路是这样class Node: def __init__(self, val): self.val val self.prev None self.next None def josephus_two_way(n: int, m: int, switch_rule) - int: # 构建双向循环链表 head Node(1) cur head for val in range(2, n 1): node Node(val) cur.next node node.prev cur cur node cur.next head head.prev cur direction 1 # 1 正向-1 反向 cur head remaining n while remaining 1: # 走 m-1 步方向由 direction 决定 for _ in range(m - 1): if direction 1: cur cur.next else: cur cur.prev last cur # 按规则决定下一轮方向 direction switch_rule(last.val, direction) # 删除 cur 节点 cur cur.next if direction 1 else cur.prev last.prev.next last.next last.next.prev last.prev remaining - 1 return cur.val这类题考的主要是“结构敏感度”你能不能意识到方向反转后指针的移动和删除动作都要相应调整。我实际写的时候犯过一个低级错误删除节点后cur 已经指向了新节点但我忘记在删除前记录 last 的指针导致后续方向判定的参照物错了。如果你在面试里遇到双向报数不要慌先跟面试官确认清楚方向切换规则然后把链表模拟的框架搭好基本能拿全分。想用数学公式秒杀这种题大概率会卡死在奇偶判断上。3.3 变体三海量数据的快速淘汰大n小m的跳步优化第三种升级变体是性能向的。当 n 达到 10^8 甚至更大而 m 很小比如 2 或 3O(n) 的线性递推虽然能跑但 10^8 次循环还是不够快。这时候需要跳步优化。思路是这样的在递推过程中当 f(i-1) 很小、i 很大时f(i) (f(i-1)m) % i 很可能不会触发取模回绕也就是说连续很多轮f 都只是单纯地加 m。比如 f 在 0 附近m2那么从 i100 到 i2000可能每一轮都是 f 2完全不需要取模。既然每一轮都是加 m我能不能一次性跳过多轮当然可以。已知当前人数为 i当前递推值为 ans若 ans m i说明本轮不用取模。我们希望找到最大的跳步数 t使得接下来 t 轮都不用取模。不取模等价于每一轮都满足ans t×m i (t-1)。解这个不等式可以得到跳步数量。实际实现时为了避免除零m1 需要单独处理。m1 时每次报数报到当前人自己也就是每轮都淘汰当前人最后剩下的一定是最后一个人编号 n。下面是完整的跳步优化版def josephus_fast(n: int, m: int) - int: if m 1: return n # 1-based ans 0 # 0-based i 2 while i n: if ans m i: # 本轮不需要取模尽量多跳 step (i - ans - 2) // (m - 1) step max(1, step) if i step n: step n - i 1 ans step * m i step else: ans (ans m) % i i 1 return ans 1这段代码的正确性我用 n10、m2 验算过普通递推结果是 51-based加速版结果也是 5。跳步版本的均摊复杂度大约是 O(m log n)当 m 远小于 n 时它的优势非常明显。比如 n10^8、m2普通递推要跑一亿次循环跳步版可能几百万次就出结果。唯一要特别注意的是 step 的最小值必须为 1否则可能死循环。我在第一次写这个优化时就是因为某个边界下 step 算出 0程序直接卡死。后来加了一个 max(1, step) 就稳了。3.4 变体对比什么时候该用模拟什么时候该用递推不少人在面试时纠结“我到底该写模拟还是递推”我一般按下面这张表来判断场景推荐方案原因n 和 m 都很小规则简单循环链表模拟直观容易解释n 大、m 固定、规则简单递推 O(n)快代码短n 很大、m 很小、规则简单跳步优化 O(m log n)在 n 更大时依然可行步长动态变化修正递推公式关键在 k 的下标映射方向反转/复杂规则双向链表模拟灵活适应各种规则记住一个核心原则能数学推导就不要纯模拟但规则复杂到推导成本过高时模拟反而是“成本更低”的选择。工程师的直觉不是选最快算法而是选“在可维护性和性能之间最平衡的算法”。4. 完整实现与高频Bug排查实录4.1 一套可直接落地的代码实现我把几种常用的实现放在一起方便你直接对照。首先是标准递推版适合日常算法题然后是循环链表版适合理解环形结构最后是跳步优化版适合性能要求高的场景。标准递推版def josephus_standard(n: int, m: int) - int: res 0 for i in range(2, n 1): res (res m) % i return res 1循环链表版class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def josephus_list(n: int, m: int) - int: head ListNode(1) cur head for val in range(2, n 1): cur.next ListNode(val) cur cur.next cur.next head cur head while cur.next ! cur: for _ in range(m - 1): cur cur.next cur.val cur.next.val cur.next cur.next.next return cur.val跳步优化版已经在上一节给过完整代码这里不再重复。要注意的是链表版里用了“把下一个节点的值复制到当前节点再删除下一个节点”的技巧避免维护前驱指针代码会更简洁。在实际项目中我更推荐把递推版封装成一个工具函数因为它的 O(1) 空间在业务里几乎是免费的。但如果是教学或规则演示链表版更直观不容易被同事质疑逻辑。4.2 5个高频Bug与排查思路第一类Bug1-based 和 0-based 混淆。症状是 n5、m2 时期望答案 3代码输出 2。排查思路非常简单在 return 之前临时 print 一下 res看是不是只差 1。如果是就把 return res 改成 return res 1。这类错误几乎每个人都会犯一次关键是养成“递推内部全用 0-based输出才转换”的习惯。第二类Bug跳步版死循环。症状是程序卡住不退出。排查时先在 while 循环开头打印 i 和 ans观察 i 是否长期不变。如果发现 i 不动大概率 step 算成了 0加一个 max(1, step) 就好。这也是我 3.3 节强调过的那次事故。第三类Bug除零错误。如果 m1跳步公式里 (m-1) 为 0直接除零。这类错误多在 n 很大的边界测试里暴露。解决方法很朴素在函数入口加一个 if m 1 的特判直接返回 n。注意是返回 n 而不是 n-1因为 1-based 输出时最后一个人就是 n。第四类Bug动态步长下标错位。症状是动态 k 数组越界或者小规模手动验证通过、大规模输出错误。核心原因是没搞清楚 k[i] 和递推轮次之间的映射关系。我建议在写动态步长时先用一个极小规模比如 n4手动模拟一遍核对每一轮 k 到底该取哪个下标再写进循环。第五类Bug双向链表删除指针错乱。症状是链表出现环内自引用输出结果不稳定。通常是删除节点时前驱和后继的指针没有同时更新或者更新顺序不对。坚持“先接桥再断开”原则先让 last.prev.next last.next再让 last.next.prev last.prev就不会漏链。4.3 问题速查表为了让排错更方便我把上面这些问题整理成一张速查表症状可能原因快速解决方案输出比期望少 10-based/1-based 混淆输出前统一 1程序死循环跳步 step 为 0加 max(1, step)除零异常m1 未特判入口判断 m1return n动态 k 结果错k 下标对应错手动模拟 n4 验证下标链表输出不稳定删除节点指针没更新好先接桥再断开这张表我在自己带新人时也发过大多数约瑟夫问题升级版的“看不懂的错”最后都能被收拢到这 5 类里。4.4 从模板到工程化的最后一步代码能跑通只是开始。如果你打算把约瑟夫环的解法真正用到工程里我建议再做一层封装把“淘汰规则”抽象成一个函数参数而不是把步长 m 写死在算法内部。比如用 Python 的话可以直接传一个 callback这样动态步长、方向反转、奇偶判断都可以变成同一套框架下的不同策略。def josephus_with_rule(n: int, initial_step: int, get_step) - int: res 0 for i in range(2, n 1): res (res get_step(i)) % i return res 1当然这个抽象在极端性能场景下会有一点额外开销但换来的可测试性非常值。如果你只是在刷题那不需要这么玩如果是写业务代码这种设计能让你的同事少踩很多坑。最后再分享一点个人经验我前前后后写过好几版约瑟夫问题升级版的实现最大的体会是这类题目考的不是“记不记得住公式”而是“能不能在规则变化时快速定位哪个环节需要跟着变”。固定步长考的是取模和编号转换动态步长考的是下标映射方向反转考的是数据结构选择海量数据考的是复杂度优化。每换一条规则就把这四个维度重新过一遍基本不会跑偏。另外如果有条件一定准备一个“暴力模拟版”作为对照。它能帮你验证递推公式和优化算法在中小规模下是否一致。我每次写跳步优化都会先用普通递推算一遍小数据再对比结果确认无误后才拿去做性能测试。这不是浪费时间而是对自己代码负责。希望这篇文章能让你少走一些我走过的弯路。