面试考到约瑟夫环大概率不是让你背个递推公式就完事而是要看你能不能从“模拟”到“数学优化”一步步说清楚以及能不能处理变体。这篇文章不搞虚的直接把这个经典问题拆开揉碎从暴力解到O(n)递推再到树状数组优化、环形链表细节、面试答题节奏一次讲透。1. 约瑟夫环问题怎么理解才是最快的1.1 一个报数游戏背后的形式化定义先把这个问题的“马甲”脱掉。约瑟夫环Josephus Problem本质上就是一群人围成一圈从某个人开始报数报到固定数字的人出局然后下一个人重新从1开始报循环往复直到只剩最后一个人或剩指定人数。这个规则听起来像小时候玩的“丢手绢”但它在算法题里的地位一点也不幼稚操作系统里的进程淘汰、缓存清理策略、数据加密的某些置换算法底层都能看到它的影子。形式化定义是这样的有 n 个人编号从 0 到 n-1或者 1 到 n两种都有下文会细说从编号为 k 的人开始报数数到 m 的人出列然后从出列者的下一个人重新报数。问最后剩下的人的编号或者要求输出完整的出列顺序。这里最容易搞混的就是“从谁开始报数”和“报到几出列”这两个参数很多人做题错就错在把 m 误当成报数次数和计数的起点混在一起。我个人的经验是拿到这类题先不要急着写代码先在草稿纸上手推一个很小的例子比如 n7、m3。把 1 到 7 围成一圈从 1 开始报数报到 3 的出列。手动推一遍出列顺序是 3、6、2、7、5、1最后剩下 4。这个例子我建议你记下来因为后面的所有代码和公式我都会用它来验证你能直观看到每一步发生了什么。1.2 为什么先讲问题模型而不是直接给公式很多资料一上来就堆递归公式读者看得一头雾水。我觉得问题模型才是最重要的因为面试官真正想考察的是你“建模”的能力。同一个约瑟夫环可以用循环链表建模可以用数组标记建模也可以用数学递推建模。三种方式对应的时间复杂度完全不同适用的场景也不同。先看一张对比表方便你建立整体认知解法思路时间复杂度空间复杂度适用场景循环链表模拟双向/单向循环链表逐个删除O(n*m)O(n)需要完整出列顺序且 n、m 都不大数组标记法visited 数组模拟报数过程O(n*m)O(n)思路最简单适合快速写出可用代码队列模拟每轮把前 m-1 个人挪到队尾O(n*m)O(n)代码量少理解成本低数学递推倒推幸存者下标O(n)O(1)只求最后幸存者n 极大也能扛树状数组二分每次快速定位下一个出列位置O(n log n)O(n)需要完整出列顺序且 n 很大这个表建议你收藏面试时如果被问到“时间复杂度多少”能立刻对号入座。另外要说明一点上面的复杂度里 n 是总人数、m 是报数间隔。当 m 很大的时候还有更极端的优化比如用取模一次跳过多轮这个后面单独展开。2. 先做暴力解法链表模拟与数组标记的完整实现2.1 链表模拟法的核心步骤与复杂度分析循环链表是最贴近题面描述的解法。你把每个人看成一个节点首尾相连走一个删一个直到只剩一个。这样写的好处是“语义”完全对齐代码不容易出逻辑错误面试时用来开场非常合适。先看核心代码Java 版自己实现一个简单链表class Node { int val; Node next; Node(int val) { this.val val; } } public int josephusLinkedList(int n, int m) { // 1. 构建循环链表 Node head new Node(1); Node prev head; for (int i 2; i n; i) { prev.next new Node(i); prev prev.next; } prev.next head; // 首尾相连 // 2. 开始报数每次移动 m-1 步后删除节点 Node cur head; Node pre prev; // pre 始终指向 cur 的前一个节点 while (cur.next ! cur) { // 从当前节点开始数 m 个人实际上只需要移动 m-1 步 for (int i 1; i m; i) { pre cur; cur cur.next; } // 删除 cur 节点 pre.next cur.next; cur pre.next; } return cur.val; }这里有两个细节特别容易踩坑。第一个是“移动多少步”的问题当前指针 cur 已经指向一个活人如果它报数为 1那么要报到 m 的人cur 应该往后移动 m-1 次。写错成 m 次就会多跳一个人。第二个是删除节点后 cur 的指向删除后 cur 应该指向被删节点的下一个节点也就是 pre.next这个节点恰好是下一轮报数的人正好延续题目“从下一个人重新报数”的语义。复杂度上每删除一个人要移动 m 次指针总共要删除 n-1 个人所以时间复杂度是 O(n*m)。当 n 和 m 都在 10^5 量级时这个解法基本跑不动。不过作为面试的第一版答案它已经足够证明你理解了题目。2.2 数组标记法的实现更简洁但同样有门槛数组标记法不用真的维护链表而是开一个布尔数组记录每个人是否还活着然后用一个指针在“逻辑上的环”里游走。代码更短但对取模运算的细节要求更高。Python 版本def josephus_array(n, m): alive [True] * (n 1) # 下标从1开始活着为True count n # 剩余人数 idx 1 # 当前报数的人 while count 1: step 0 while step m: if alive[idx]: step 1 if step m: break idx idx % n 1 # 环形移动 alive[idx] False count - 1 idx idx % n 1 # 从下一个人重新开始 # 找出唯一幸存者 for i in range(1, n 1): if alive[i]: return i return -1这里最容易出问题的就是环形的移动方式。我用的是idx idx % n 1它等价于“如果 idx 是 n就回到 1否则加 1”。你要注意这个写法里 idx 是从 1 到 n 循环的不是从 0 到 n-1所以取模的时候要格外小心。如果你习惯 0 下标也可以用idx (idx 1) % n但这样数组要多留一个位置。数组标记法和链表模拟的时间复杂度一样都是 O(n*m)但空间上数组更省因为不需要存储指针。不过在 n 很大的时候这个“模拟”的思路无论如何都撑不住所以才需要数学递推来救场。3. O(n) 进阶解法从数学递推里看穿约瑟夫环的本质3.1 递推公式是怎么一步一步推出来的数学递推的思路不是“模拟删除”而是“反过来看幸存者的位置变化”。假设 n 个人的编号是 0 到 n-1每次数到 m 的人出列。第一轮出列的人编号是 (m-1) mod n。删掉他之后剩下 n-1 个人但是编号已经不是原来的 0 到 n-1 了而是从m mod n开始的一个新序列。关键一步来了如果我们把剩下的 n-1 个人重新编号为 0 到 n-2那么“在 n-1 规模下最后幸存者的新编号”和“在 n 规模下最后幸存者的原编号”之间存在一个固定的映射关系。设 f(n, m) 表示 n 个人、间隔 m 时最后幸存者的原编号0-based那么有f(1) 0 f(n) (f(n-1) m) % n这个式子看起来简单但推导逻辑一定要自己走一遍。我来解释删掉第一个人后下一轮从编号为 m mod n 的人开始相当于整个序列向左平移了 m 个位置。如果我们在 n-1 规模下已经知道幸存者的“新编号”是 f(n-1)那么映射回原来的编号就要加上 m 再对 n 取模。用 n7、m3 验证一下f(1)0f(2)(03)%21f(3)(13)%31f(4)(13)%40f(5)(03)%53f(6)(33)%60f(7)(03)%73。0-based 的 3 对应 1-based 的 4和我们前面手动推的结果一致。3.2 递归与迭代两种写法以及 1-based 编号的坑根据递推公式可以有两种代码实现。先看递归def josephus_recursive(n, m): # 返回 0-based 的幸存者编号 if n 1: return 0 return (josephus_recursive(n - 1, m) m) % n递归写法很漂亮但 n 很大时会有递归栈溢出的风险Python 默认递归深度只有 1000 左右。所以更推荐迭代版def josephus_iterative(n, m): survivor 0 for i in range(2, n 1): survivor (survivor m) % i return survivor注意循环变量 i 从 2 到 n每一步对应的就是“当前规模下”的人数。这个循环体的意思是已知 i-1 规模下的幸存者下标为 survivor现在规模扩大到 i同一个人在新一圈里的下标就是(survivor m) % i。还要回答一个高频问题题目如果要求 1-based 编号怎么办最简单的是用公式算出 0-based 结果然后加 1。不要试图在递推公式里直接套 1-based容易把自己绕晕因为取模运算对 0-based 是最自然的。3.3 优化 m 很大的情况取模跳步有时候面试官会追加一个条件n 很大m 也很大比如 n10^9、m10^18。这时 O(n) 也扛不住但这个条件反而透露出一个信号——很多轮里没人出局。思路是当前有 cur_n 个人从当前位置开始报数如果 m 远大于 cur_n那么实际上会绕很多圈但第一次有人出局时位置就是(pos m) % cur_n。我们可以一次性算出“在不删除任何人的情况下指针完整绕了多少圈、最后落在哪里”然后用取模做到一次跳过多圈。具体实现可以这样如果 m 比 cur_n 大先计算从当前轮到下一次出局需要移动的步数等价于前进一步就计数一次所以仍需要m-1步移动但我们可以用数学方式跳过大量循环。不过这里有个更常见的工程做法直接利用递推公式的周期性或者用“分段跳跃”def josephus_fast(n, m): # 从 cur_n1 开始倒推但 m 很大时跳过 survivor 0 cur_n 1 while cur_n n: # 在当前规模 cur_n 下幸存者游标为 survivor # 要扩大规模下一轮有 cur_n 1 个人 # 如果 m 很大一次可以扩大很多个规模直到出现“同一轮不需要取模”的边界 if m % (cur_n 1) 0: survivor (survivor m) % (cur_n 1) cur_n 1 else: # 可以批量跳的优化这里从简处理 survivor (survivor m) % (cur_n 1) cur_n 1 return survivor严格来说跳跃式优化需要根据 m 与 cur_n 的关系计算一个“可以连续扩展 k 步而不会跨越取模周期”的阈值代码会复杂一些。面试里一般只要你能说出“m 很大时可以用取模减少无效轮次”这个思路就够了不需要完整实现但能写出来绝对是加分项。4. 进阶变体与实战拓展约瑟夫环还能怎么考4.1 要求输出完整出列顺序时用树状数组加二分很多场景不只是要最后一个幸存者而是要整个出列顺序。这时候 O(n) 递推公式就帮不上忙了因为它只追踪了一个人的命运其他人的过程全被丢弃。如果 n 不大直接用第一节的链表模拟即可但如果 n 在 10^5 甚至 10^6 量级O(n*m) 就不行了。工程上常用的是“树状数组Fenwick Tree 二分查找”的思路。我们用树状数组维护每个位置的存活状态活人记为 1删掉后更新为 0。每次要找“下一个出列的人”就是在当前指针位置的基础上再数 m 个活人等价于在树状数组的“前缀和”序列里二分查找第 k 个 1 的位置。class Fenwick: def __init__(self, n): self.n n self.bit [0] * (n 1) for i in range(1, n 1): self.bit[i] 1 j i (i -i) if j n: self.bit[j] self.bit[i] def add(self, idx, delta): while idx self.n: self.bit[idx] delta idx idx -idx def sum(self, idx): s 0 while idx 0: s self.bit[idx] idx - idx -idx return s def find_kth(self, k): # 二分查找前缀和 k 的最小位置 lo, hi 1, self.n while lo hi: mid (lo hi) // 2 if self.sum(mid) k: hi mid else: lo mid 1 return lo def josephus_order(n, m): bit Fenwick(n) result [] cur 1 # 当前起点1-based remain n for _ in range(n): # 从 cur 开始还需要数 m 个活人但是因为环状 # 我们先计算当前位置之前有多少活人 before bit.sum(cur - 1) k (before m) % remain if k 0: k remain idx bit.find_kth(k) result.append(idx) bit.add(idx, -1) remain - 1 cur idx # 删除位置的下一个活人作为下一轮起点 if remain 0: break return result这个做法的时间复杂度是 O(n log n)可以轻松应对几十万量级的输入。它的思路本质上还是“模拟”但是用数据结构把“找到下一个要删除的人”的操作从 O(m) 降到了 O(log n)。如果你在面试里写到这里面试官通常会眼前一亮因为很多人连树状数组都不熟练。4.2 约瑟夫环思想在实际系统的映射除了刷题约瑟夫环的思想在很多系统中真实存在。比如操作系统里的“时间片轮转”调度进程排成一个环形队列每个进程运行一个时间片时间到了就换下一个如果进程结束就出队——这和约瑟夫环的“报到即出列”简直一模一样只是这里的 m 变成了时间片长度产生的时间点变成了进程结束。再比如 Redis 里淘汰数据的某些策略或者游戏匹配中的“轮询剔除”底层都有类似的环形遍历逻辑。理解约瑟夫环的“环状游走 条件淘汰”模型对看很多中间件的源码会有帮助。还有一个经典延伸是“加密算法”。有些置换算法会把明文按环形规则重新排列置换的步长就类似这里的 m。虽然不是标准叫法但数学本质完全一致。面试时如果能主动提一两个这类映射场景会显得你的视野不是停留在“算法题”本身。5. 常见错误、调试技巧与面试应对实录5.1 新人最容易踩的五个坑我自己带过不少人写约瑟夫环发现这几个错误反复出现我整理成一张问题速查表错误现象根本原因解决方案删除时多跳一个人从当前人开始计数但代码移动了 m 次确认移动 m-1 次输入 n1 时返回错误没有处理边界条件特判 n1 返回 1 或 0下标越界1-based 和 0-based 混用统一用一种编号体系循环链表删除后死循环删除后指针没有正确指向下一个活人删除后用 pre.next 作为下一次起点m 大于 n 时结果不对没有对 m 取模或者取模时机不对在递推中每次都用(survivor m) % ii 为当前人数还有一个细节很多人问“m1 时怎么办”。如果 m1那就是从当前人开始直接出列最后剩下的人是当前人的下一个人当 n1 时。用递推公式也能算f(n) (f(n-1)1) % n算出来 n 个人的幸存者是 n-10-based也就是编号最大的那个人。手动推一下就会发现这个结果是对的因为每次删的都是“当前人”最后一定剩下最后一个没有被轮到的人。5.2 面试和竞赛中的答题节奏建议如果是面试我建议按这个节奏来先花一两分钟跟面试官确认输入输出尤其是编号从 0 开始还是 1 开始、是否需要完整出列顺序、n 和 m 的取值范围。然后第一版给出链表或数组模拟把复杂度说清楚。接着主动提出“题目如果只要最后一个幸存者可以用 O(n) 的递推优化”直接写出迭代版。大多数面试官到这里就满意了。如果面试官继续追问“n 很大怎么办”你再把 m 很大时的取模跳跃思路抛出来。不要一上来就写树状数组因为面试官可能觉得你想秀技但没考虑问题的实际需求。先暴力、再优化、最后讨论边界和扩展这个递进本身就是考察点。竞赛场景下则相反直接根据数据范围选算法。看清 n 和 m 的量级n 在 10^5 以内要完整序列用树状数组只要最后的幸存者直接 O(n) 递推。我见过不少选手在简单题上纠结半天结果最后发现直接用递推公式两行代码就过了浪费时间在复杂实现上。5.3 我调试约瑟夫环的一个独门技巧最后分享一个我自己的小习惯每次写完约瑟夫环代码我都会在一张纸上先手动跑一个 n7、m3 的例子然后把程序的输出和手推结果对比。这个例子足够小能肉眼验证又足够大能暴露“少删一个”“多移一位”这类问题。很多人喜欢随机造大数测试反而不好定位错误因为手算根本跟不上了。如果程序结果不对我的排查顺序是这样的先检查删除时的指针移动步数再检查取模运算的换算然后检查删除后下一轮起点的指向最后检查边界条件。这四步能解决九成以上的 bug。还有一个小技巧在链表模拟的循环里打印每一步删除的节点值和当前存活节点能瞬间看到是哪个环节逻辑偏了比单纯看最终结果直觉得多。实际写工程代码时如果确定要处理超大 n我不会手写链表而是直接用现成的平衡树或 Fenwick 库因为手写链表在内存分配频繁的场景下性能并不好。而且生产环境里的“人数”可能动态变化比如进程列表中间会不断有新进程加入这时候静态的约瑟夫环模型就需要改成动态数据结构的变体这也是我为什么一直强调“理解模型比背代码更重要”的原因。