约瑟夫环问题全解析：从链表模拟到O(n)递推与树状数组优化

面试考到约瑟夫环，大概率不是让你背个递推公式就完事，而是要看你能不能从“模拟”到“数学优化”一步步说清楚，以及能不能处理变体。这篇文章不搞虚的，直接把这个经典问题拆开揉碎，从暴力解到O(n)递推，再到树状数组优化、环形链表细节、面试答题节奏，一次讲透。

1. 约瑟夫环问题怎么理解才是最快的

1.1 一个报数游戏背后的形式化定义

先把这个问题的“马甲”脱掉。约瑟夫环（Josephus Problem）本质上就是一群人围成一圈，从某个人开始报数，报到固定数字的人出局，然后下一个人重新从1开始报，循环往复，直到只剩最后一个人（或剩指定人数）。这个规则听起来像小时候玩的“丢手绢”，但它在算法题里的地位一点也不幼稚，操作系统里的进程淘汰、缓存清理策略、数据加密的某些置换算法，底层都能看到它的影子。

形式化定义是这样的：有 n 个人，编号从 0 到 n-1（或者 1 到 n，两种都有，下文会细说），从编号为 k 的人开始报数，数到 m 的人出列，然后从出列者的下一个人重新报数。问最后剩下的人的编号，或者要求输出完整的出列顺序。这里最容易搞混的就是“从谁开始报数”和“报到几出列”这两个参数，很多人做题错就错在把 m 误当成报数次数和计数的起点混在一起。

我个人的经验是：拿到这类题先不要急着写代码，先在草稿纸上手推一个很小的例子，比如 n=7、m=3。把 1 到 7 围成一圈，从 1 开始报数，报到 3 的出列。手动推一遍，出列顺序是 3、6、2、7、5、1，最后剩下 4。这个例子我建议你记下来，因为后面的所有代码和公式，我都会用它来验证，你能直观看到每一步发生了什么。

1.2 为什么先讲问题模型而不是直接给公式

很多资料一上来就堆递归公式，读者看得一头雾水。我觉得问题模型才是最重要的，因为面试官真正想考察的是你“建模”的能力。同一个约瑟夫环，可以用循环链表建模，可以用数组标记建模，也可以用数学递推建模。三种方式对应的时间复杂度完全不同，适用的场景也不同。

先看一张对比表，方便你建立整体认知：

这个表建议你收藏，面试时如果被问到“时间复杂度多少”，能立刻对号入座。另外要说明一点，上面的复杂度里 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 取模。

用 n=7、m=3 验证一下：f(1)=0；f(2)=(0+3)%2=1；f(3)=(1+3)%3=1；f(4)=(1+3)%4=0；f(5)=(0+3)%5=3；f(6)=(3+3)%6=0；f(7)=(0+3)%7=3。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 也很大，比如 n=10^9、m=10^18。这时 O(n) 也扛不住，但这个条件反而透露出一个信号——很多轮里没人出局。

思路是：当前有 cur_n 个人，从当前位置开始报数，如果 m 远大于 cur_n，那么实际上会绕很多圈，但第一次有人出局时，位置就是(pos + m) % cur_n。我们可以一次性算出“在不删除任何人的情况下，指针完整绕了多少圈、最后落在哪里”，然后用取模做到一次跳过多圈。

具体实现可以这样：如果 m 比 cur_n 大，先计算从当前轮到下一次出局需要移动的步数，等价于前进一步就计数一次，所以仍需要m-1步移动，但我们可以用数学方式跳过大量循环。不过这里有个更常见的工程做法：直接利用递推公式的周期性或者用“分段跳跃”：

def josephus_fast(n, m): # 从 cur_n=1 开始倒推，但 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=1 时怎么办”。如果 m=1，那就是从当前人开始直接出列，最后剩下的人是当前人的下一个人（当 n>1 时）。用递推公式也能算：f(n) = (f(n-1)+1) % n，算出来 n 个人的幸存者是 n-1（0-based），也就是编号最大的那个人。手动推一下就会发现，这个结果是对的，因为每次删的都是“当前人”，最后一定剩下最后一个没有被轮到的人。

5.2 面试和竞赛中的答题节奏建议

如果是面试，我建议按这个节奏来：先花一两分钟跟面试官确认输入输出，尤其是编号从 0 开始还是 1 开始、是否需要完整出列顺序、n 和 m 的取值范围。然后第一版给出链表或数组模拟，把复杂度说清楚。接着主动提出“题目如果只要最后一个幸存者，可以用 O(n) 的递推优化”，直接写出迭代版。大多数面试官到这里就满意了。

如果面试官继续追问“n 很大怎么办”，你再把 m 很大时的取模跳跃思路抛出来。不要一上来就写树状数组，因为面试官可能觉得你想秀技但没考虑问题的实际需求。先暴力、再优化、最后讨论边界和扩展，这个递进本身就是考察点。

竞赛场景下则相反，直接根据数据范围选算法。看清 n 和 m 的量级，n 在 10^5 以内要完整序列，用树状数组；只要最后的幸存者，直接 O(n) 递推。我见过不少选手在简单题上纠结半天，结果最后发现直接用递推公式两行代码就过了，浪费时间在复杂实现上。

5.3 我调试约瑟夫环的一个独门技巧

最后分享一个我自己的小习惯：每次写完约瑟夫环代码，我都会在一张纸上先手动跑一个 n=7、m=3 的例子，然后把程序的输出和手推结果对比。这个例子足够小，能肉眼验证；又足够大，能暴露“少删一个”“多移一位”这类问题。很多人喜欢随机造大数测试，反而不好定位错误，因为手算根本跟不上了。

如果程序结果不对，我的排查顺序是这样的：先检查删除时的指针移动步数，再检查取模运算的换算，然后检查删除后下一轮起点的指向，最后检查边界条件。这四步能解决九成以上的 bug。还有一个小技巧，在链表模拟的循环里打印每一步删除的节点值和当前存活节点，能瞬间看到是哪个环节逻辑偏了，比单纯看最终结果直觉得多。

实际写工程代码时，如果确定要处理超大 n，我不会手写链表，而是直接用现成的平衡树或 Fenwick 库，因为手写链表在内存分配频繁的场景下性能并不好。而且生产环境里的“人数”可能动态变化，比如进程列表中间会不断有新进程加入，这时候静态的约瑟夫环模型就需要改成动态数据结构的变体，这也是我为什么一直强调“理解模型比背代码更重要”的原因。