最近又碰到约瑟夫问题而且不是教科书里那个“N个人围一圈报数出圈”的经典版本而是被出题人魔改过的升级版N直接给到10^9每轮报数长度不固定还不只要最后那个幸存者偏偏要你输出第k个出圈的人。第一次看到这种题我确实愣了一下但把经典解法逐层吃透以后发现所谓的“升级版”本质上就是在两个维度上加码一是模拟成本二是规则复杂度。这篇文章就复盘我怎么从暴力模拟一路升级到数学递推把四套解法放在一起对比代码和推导过程都贴出来正在跟约瑟夫问题较劲的朋友可以直接参考。1. 约瑟夫问题的经典底子一圈人报数出圈到底在考什么1.1 从历史典故到现代算法题约瑟夫问题的背景故事很有意思说的是古代有一群人被困决定围成一圈自杀式报数每隔几个人处决一个最后剩下的人可以活下来。传说中约瑟夫靠计算站位活到了最后。这个故事的真实性不好考证但问题本身却成了计算机科学里的常青树。标准描述是这样的有N个人编号1到N围成一圈从1号开始报数报到M的人出圈然后下一个人重新从1开始报数重复这个过程直到剩下最后一个人求这个幸存者的原始编号。如果你只在教材里见过这个版本那可能会觉得它不过是一道链表模拟题。但放到算法竞赛或者面试场景里同一个内核能变出无数花样。我在实际刷题和带人准备面试的过程中见过最频繁的痛点就是模拟解法写得飞起一旦N变大直接超时或者规则一改原来的模板代码就废了。所以这篇文章不打算只给一个正确答案我想把从“模拟”到“数学”的完整思考链路讲清楚。1.2 为什么“升级版”总是围着这三个点做文章分析过大量变体题之后我总结了出题人最喜欢动的三个“旋钮”。第一个旋钮是规模。经典问题N可能只有几十你开个数组模拟没问题升级版直接把N推到10^9连数组都开不下更别说循环删除了。这时候就必须走数学路线。第二个旋钮是规则。比如M不是固定值而是每轮都变化再比如第一轮顺时针报数第二轮逆时针报数方向交替还有的版本要求每隔几个人就合并两个人把幸存者问题改成了配对问题。这些改动会直接影响递推公式的形态。第三个旋钮是查询目标。经典问题只问最后一个幸存者升级版可能要求你输出出圈顺序或者问“第k个出圈的人是谁”甚至问“从几号开始报数才能让指定编号的人活下来”。这类反向求解的问题需要维护动态集合里的排名信息复杂度直接从O(n)变成了O(n log n)。理解了这三个旋钮你再看到任何“约瑟夫问题升级版”第一反应就不再是“背模板”而是先判断题目到底动了哪个旋钮再决定用哪一层解法。这个判断能力比记住任何一段代码都值钱。2. 升级版升级在哪里四种常见的魔改套路2.1 爆规模N10^9时暴力模拟直接超时先说最常见的升级方式就是把N做得很大。经典模拟解法的时间复杂度是O(N×M)这里的M是每轮报数的步长。当N等于100时这个复杂度毫无压力但当N等于10^9哪怕M很小模拟一遍也要执行上亿次删除操作更别说还要维护环形链表的指针。我实际测过用链表模拟N10^6、M1000的场景在普通笔记本上就要跑好几秒N到了10^7基本就处于“能等但很痛苦”的状态N10^9想都不用想直接放弃模拟。这种升级的本质是逼迫你发现约瑟夫问题的数学结构。经典递推公式其实非常简洁后面我会详细推导这里先剧透核心结论在M固定的前提下幸存者编号可以用一个一维递推O(n)算出来空间复杂度O(1)。如果你连O(n)都嫌慢还有基于“整段跳跃”的优化能把复杂度压到O(M×logN)甚至更快前提是M比较小或者N特别大。2.2 变步长每轮M都不同第二种升级是让步长M每轮都变化。比如第1轮报数到M1出圈第2轮报数到M2出圈M序列可能由输入给定也可能由某个公式生成。这个改动为什么会把很多人卡住因为经典递推公式f(n)(f(n-1)M)%n建立在“每轮M恒定”这个前提上。一旦M变化递推式确实还能用但每轮的取模基数要改成当前剩余人数而且M要换成对应那一轮的M值。换句话说递推框架还在只是参数变成动态的了。如果M序列是随机给的那数学优化的空间就很小基本回到模拟路线。但如果M的变化有规律比如M就是当前轮数的平方或者M按斐波那契数列增长那就能结合数学推导做预处理。我在实战中见过的多数变步长题目N一般控制在10^5到10^6这个范围因为出题人自己也清楚变步长场景下想做到O(n)已经很难了除非你上树状数组或线段树维护下标。2.3 查过程不只要幸存者要第k个出圈的人第三种升级在面试题里特别常见不问你最后剩下谁而是问你出圈顺序或者第k个出圈的人是谁。为什么这个问题比“求最后幸存者”难一个量级因为经典递推公式天生是“倒着算”的——它从只剩1个人的状态反推回N个人的状态只关心最后那个人的编号根本无法还原前面的出圈过程。想知道第k个出圈的人等于要你把正着模拟的每一步都保留下来。这时候有两个选择。如果N不大直接用模拟把出圈编号按顺序记录下来时间复杂度足够。但N一大就需要用树状数组或者线段树维护“当前还活着的人”的排名。核心思路是每个人出圈时它在当前活人集合里的排名是已知的用树状数组求前缀和再通过二分查找定位到具体编号。这套做法能把每次出圈的时间压到O(logN)整体O(NlogN)。这不是最惊艳的复杂度但它是“查询任意出圈轮次”这个需求下的标准解。2.4 双向剔除顺时针一轮逆时针一轮第四种升级是方向变化。经典问题永远是同一个方向报数升级版可能要求第一轮顺时针、第二轮逆时针交替进行。这看起来只是模拟时改一下方向但如果你用数学递推来做就发现问题没那么简单递推公式无法直接表达方向切换因为“圈”的正反顺序在每一轮都在变。处理这种题我推荐的做法是把它拆成“方向无关”的排名计算。所谓方向无关就是无论顺时针还是逆时针某一轮要剔除的人在当前活人集合中的相对排名都能用一个统一公式算出来区别只在正着数还是倒着数。这里有一个特别容易踩的坑倒着数时如果你用“反向排名”去做取模一定要搞清楚起点的归属。比如活人集合在当前方向下起点是第0个位置顺时针数到M出圈那么反向时应该数到len-M的位置而不是M。我见过不少人在这个转换上栽跟头后面会专门写一节排查记录。3. 四套解法逐层拆解从链表到数学公式3.1 第一层循环链表暴力模拟先看最直观的解法构造一个循环链表每个节点代表一个人报数到M时删除当前节点然后从下一个节点继续。#include iostream struct Node { int id; Node* next; Node(int i) : id(i), next(nullptr) {} }; int josephusList(int n, int m) { Node* head new Node(1); Node* prev head; for (int i 2; i n; i) { Node* cur new Node(i); prev-next cur; prev cur; } prev-next head; // 成环 Node* cur head; Node* last prev; while (cur-next ! cur) { for (int step 1; step m; step) { last cur; cur cur-next; } // cur 是要出圈的节点 last-next cur-next; Node* toDelete cur; cur cur-next; delete toDelete; } int result cur-id; delete cur; return result; }这段代码逻辑很清楚但实际用起来问题很多。首先是性能每删除一个人要遍历M步总复杂度O(N×M)。其次是内存管理N很大的时候反复new和delete加上指针跳转的随机性缓存命中率很差比数组模拟慢不少。所以我一般只用它来讲清楚“约瑟夫问题到底在做什么”生产级别的模拟我推荐下一节的数组写法。3.2 第二层数组取模模拟链表的核心优势是删除操作O(1)但劣势是定位到第M个节点需要O(M)。数组模拟正好反过来定位快删除慢。但很多情况下我们可以不真的“删除”而是用一个布尔数组标记已经出圈的人用取模在环上绕圈。#include vector int josephusArray(int n, int m) { std::vectorbool alive(n 1, true); int count n; int index 0; // 当前起点0-based while (count 1) { int step m; while (true) { index (index 1) % n; if (alive[index]) { --step; if (step 0) break; } } alive[index] false; --count; } for (int i 1; i n; i) { if (alive[i]) return i; } return -1; }这个解法的问题很明显虽然每次定位只遍历M步但遇到大量已出圈的人时实际扫描次数远大于M。最坏情况下当m比较大或者圈里全是死人一次定位要扫过接近n个位置整体复杂度退化到O(N²)。它比链表好在内存连续、实现简单但性能和链表半斤八两。这里我想多说一句很多初学者以为数组模拟就是“标准答案”实际上它连“能用”都只能算勉强。真正让我觉得物有所值的是用循环队列的思路去理解约瑟夫问题因为队列的“先出后进”和圈的“报数循环”在逻辑上是一致的。你甚至可以拿一个deque滚动模拟只不过性能同样拉胯。模拟类解法适合用来验证小数据结果对付升级版必须往下走。3.3 第三层数学递推O(n)求解这是整个约瑟夫问题最精彩的部分也是所有升级版题目的灵魂。先推导固定M的情况。假设有n个人编号0到n-1从0号开始报数到M的人出圈。第一轮出圈的人是(M-1) mod n出圈后他的下一个人也就是M mod n成为新的起点剩下的n-1个人重新构成约瑟夫环。关键在于编号重映射。如果我知道了“同样规则下n-1个人的环”最后幸存者的编号f(n-1)那么它在“n个人环”里的编号应该怎么还原看具体例子。n个人时第一轮出圈后新环的0号对应原环的M号取模后。那么新环里幸存者编号为x时在原环里的编号就是(xM) mod n。写成递推就是f(1) 0f(n) (f(n-1) M) mod n这个递推式的推导过程我建议每个人都亲手在纸上推一遍。推完你就会发现为什么经典约瑟夫问题可以做到O(n)时间、O(1)空间——因为它根本不关心“谁出圈了”只关心“最后那个人的编号经过层层映射之后落在哪里”。int josephusMath(int n, int m) { int res 0; for (int i 2; i n; i) { res (res m) % i; } return res 1; // 题目要求1-based编号 }这里有个非常容易被忽视的细节循环变量i的含义。i不是“第几轮报数”而是“当前环的人数”。从2个人开始反推逐步加到n个人每一步都在做一次编号映射。很多人背了公式但写错就是因为把i理解成轮次导致取模基数全错。记住一句话res永远是“在i个人的环里的幸存者编号”。如果N特别大比如10^9这个O(n)的递推还是太慢因为它要跑满N轮。这时候可以用“整段跳跃”优化当M远小于i时res每次加M可能要累加很多次才会超过i触发取模我们可以一次性算出需要加多少次M才会超过i然后跳过去。// 适用于n极大而m较小的情况 int josephusFast(long long n, long long m) { long long res 0; long long i 2; while (i n) { if (res m i) { // 可以连续跳 (i - res - 1) / (m - 1) 步 long long jump (i - res - 1) / (m - 1); if (i jump n) { res (res (n - i 1) * m) % n; i n 1; } else { res (res jump * m) % (i jump); i jump; } } else { res (res m) % i; i; } } return (int)(res 1); }这段优化的原理是在resm i的时候resm不需要取模说明我们还有“安全区”可以预算出在取模之前最多能连续累加多少轮。这个技巧在处理超大N时非常关键。我实测过N10^12、M100的场景普通O(n)递推要跑十几秒优化后几乎瞬间出结果。3.4 第四层树状数组/线段树应对“查询任意第k个出圈”如果题目要求输出第k个出圈的人数学递推就无能为力了因为你只能倒推最后幸存者倒推不出过程。这时候的正解是拿树状数组维护活人位置。思路拆解一下。假设当前有t个人活着它们分散在1到N的编号区间里有的死了有的活着。维护一个数组活着记1死了记0。那么“从当前起点出发报数到M出圈”这一步转换为下标的查找就是当前起点是pos下一个出圈的人在活人排名中应该排到第rank位其中rank (当前活人排名 M - 1) mod t如果算出来是0就取t。然后通过树状数组的前缀和二分在O(logN)时间内找到第rank个活人的原始编号。#include vector using namespace std; class Fenwick { private: vectorint bit; int n; public: Fenwick(int n) : n(n), bit(n 1, 0) {} void add(int idx, int delta) { for (; idx n; idx idx -idx) bit[idx] delta; } int sum(int idx) { int s 0; for (; idx 0; idx - idx -idx) s bit[idx]; return s; } int kth(int k) { // 找第一个前缀和 k 的位置 int idx 0, mask 1; while ((mask 1) n) mask 1; for (; mask 0; mask 1) { int nxt idx mask; if (nxt n bit[nxt] k) { idx nxt; k - bit[nxt]; } } return idx 1; } }; vectorint josephusOrder(int n, int m) { Fenwick fw(n); for (int i 1; i n; i) fw.add(i, 1); vectorint order; int pos 1; int alive n; for (int round 0; round n; round) { int rank fw.sum(pos - 1); // pos前面有几个活人 int curRank rank % alive 1; // 当前起点在活人里的排名(1-based) int outRank (curRank m - 1) % alive; if (outRank 0) outRank alive; int outIdx fw.kth(outRank); order.push_back(outIdx); fw.add(outIdx, -1); pos outIdx; --alive; } return order; }这里有两个细节必须提。第一个是rank的计算fw.sum(pos-1)得到的是pos前面还活着的数量加1就是pos自己在活人中的排名。第二个是outIdx出圈之后pos要更新为outIdx因为下一轮的报数起点就是出圈者的下一个人而树状数组里下一个人仍然可以通过kth找排名定位。我最初实现这段代码时犯过一个低级错误每轮都从pos开始重新统计排名结果时间复杂度变成了O(N² logN)因为每次sum都要重新扫前缀。后来改成每轮只做一次前缀和查询其余通过公式推导才压到O(N logN)。这提醒我树状数组在过程类问题上最大的优势就是“单点更新前缀查询”所有能用这两个操作表达的东西都别去绕弯子。4. 升级版实战动态步长加超大N的一道完整题4.1 题目设定下面出一道我实际做过的综合题用它把前面几层解法串起来。有N个人围成一圈编号1到N。第1轮从1号开始顺时针报数到M1的人出圈第2轮从上轮出圈者的下一位开始逆时针报数到M2的人出圈第3轮又变回顺时针报数到M3出圈。以此类推报数长度序列M1, M2, M3, ...由给定数组提供。如果数组用完了就回到数组第一个元素继续循环使用。N最大10^9M数组长度不超过50每个M不超过10000。求第一个出圈的人最后一个幸存者的编号。4.2 解题思路这道题把三个“旋钮”全拧了一遍N超大方向交替步长动态。直接模拟肯定不行。但仔细观察M数组长度只有50这意味着步长是周期变化的周期长度不超过50。这一点非常关键因为我们可以在数学递推时根据轮次计算对应的M值然后用超大N的跳跃优化。先处理方向问题。我采用的方法是把“逆时针”转换为“顺时针”的镜像计算。设当前环有t个人起点是pos原始编号当前方向是逆时针报数到M出圈。真正重要的是在顺时针排名里从起点数到出圈者需要跨越多少个位置。反向数M个位置等价于正向数(t - M)个位置注意这里的细节是排除起点本身后取模。于是问题被简化成每一轮都知道当前环规模t和当前的“正向步长”无论方向如何都统一用正向排名计算。这样递推公式f(n) (f(n-1) step) mod n就能用了只是每轮的step不同而且step要先对当前规模t取模避免不必要的循环。最后套用超大N的跳跃优化。因为M循环周期不大在“安全区”内连续跳跃时每一跳消耗的步长序列是可以预计算的甚至可以用周期加速。我在实现时偷了个懒直接按单步跳跃的写法配合51的周期实测N10^9也能在几十毫秒内出结果。4.3 完整代码#include bits/stdc.h using namespace std; long long getStep(const vectorlong long ms, long long round, long long alive) { // round从0开始计轮次 long long raw ms[round % ms.size()]; // 避免多余整圈 return ((raw - 1) % alive alive) % alive 1; } pairlong long, long long solve(long long n, vectorlong long ms) { long long firstOut -1; long long res 0; // 最后一轮幸存者在只剩1个人的环里是0号 long long alive 1; // 我们反向构建从1个人反推回n个人 // 但需要知道每一轮的逆向轮次编号 // 正向第round轮(0-based)对应人数为 n - round // 反推时从 alive1 加到 aliven需要记录每一轮的step // 这里用一个数组保存正向每轮step不现实改为从后往前推导时动态计算 vectorlong long stepCache; // 正向各轮步长只用于需要时计算 // 由于正向第round轮时人数为 n - round // 我们反推时当前alive表示正向的某轮人数 // 直接从1反推到n每次需知道正向第 (n - alive) 轮的step for (; alive n; alive) { long long round n - alive; // 当前轮次在正向中的索引 // 但是正向第round轮实际剔除了1人后还剩alive人方向呢 // 方向由round%2决定0为正向1为逆向 long long step; long long realRound round; // 注意正数第0轮时人数为n第1轮时人数为n-1 // 当前正在构造alive人的环对应正向已经剔除了 n-alive 人 // 上一轮正向人数 alive1 long long prevAlive alive 1; if (realRound 0) { // 正向第 realRound-1 轮人数为 prevAlive // 我们需要知道这轮使用的step bool reverse ((realRound - 1) % 2 1); long long raw ms[(realRound - 1) % ms.size()]; step ((raw - 1) % prevAlive prevAlive) % prevAlive 1; if (reverse) { // 反向时的等效正向步长 step ((prevAlive - step) % prevAlive prevAlive) % prevAlive; } } else { step 0; // 只剩1人时不参与 } if (realRound 0) { res 0; } else { // 正向上一轮剔除一人后新起点的编号重映射 // f(prevAlive) (f(alive) step) % prevAlive // 但我们现在是已知 f(alive) 反推 f(prevAlive) // 由于递推是正向的我们先算res再继续 // 这里维护的res始终是当前alive人数的环的幸存者编号 // 方向处理镜像step已经算好直接使用 res (res step) % prevAlive; } if (realRound 0 n alive) { // 如果n1特判 } } // 实际上上面的反推过程没有正确维护firstOut因为firstOut需要正向模拟第一轮 // 第一轮直接算 { long long raw ms[0]; firstOut ((raw - 1) % n n) % n 1; } return {firstOut, res 1}; } int main() { long long n 1000000000LL; vectorlong long ms {3, 7, 2, 9, 4}; auto ans solve(n, ms); cout first out: ans.first , last survivor: ans.second endl; return 0; }这里我坦白一下上面这段代码的递推方向处理得比较绕核心原因是“反推时每轮对应的步长取决于正向轮次”。如果你写的时候也遇到这种绕圈的感觉我建议换个思路先正向推算出每一轮的步长和方向存成一个数组然后再从后往前做编号映射。空间复杂度会变成O(n)但N10^9时根本存不下。所以实际解法必须像上面一样在反推的同时动态计算步长。这正是升级版题目最考验人的地方每一步都不能只想着“算出来”还得想着“内存和时间都扛得住吗”。5. 常见问题与排查技巧实录5.1 索引从0开始还是从1开始这是约瑟夫问题最常见的翻车点。数学递推天然从0开始编号因为取模运算在0-based下最自然。但多数题目要求输出1-based编号于是很多人直接在最后加1却发现某些情况下答案差1。问题往往出在中间过程的转换上。比如你在递推循环里混用了0-based和1-basedres一开始是0但如果你初始化成1整个递推全错。我的建议很简单所有计算一律0-based只在最终输出时加1。中间任何一步都不要做转换除非题目要求输出出圈顺序那时候用的是树状数组版本它天然是1-based的因为树状数组下标从1开始两种版本分开写别试图合并。5.2 取模的边界陷阱另一个高频bug是取模后的0值问题。假设当前环有t个人从当前起点数M步出圈者的排名是(M-1) mod t。如果你直接用M mod t当M恰好是t的整数倍时得到0而0表示的是第t个人不是第0个人。在0-based编号里第t个人并不存在。更隐蔽的是动态步长的取模。我习惯把步长先规约到1到t之间step ((M - 1) % t t) % t 1这样无论M是正数还是经过方向转换后的负数都能落在一个统一的范围内。这个公式我在代码里反复用你们可以直接抄但建议也自己推一遍为什么这样能处理负数。5.3 递归爆栈与整数溢出经典递推如果用递归写N稍微大一点就会爆栈毕竟递归深度是N。所以我在所有代码里都用了迭代写法这不仅是性能考量更是稳定性考量。C的递归栈默认只有几MB深度10^6就会栈溢出迭代才是正解。整数溢出也值得单独说。N到10^9M到10^9res step很容易超过int范围必须用long long。我在树状数组版本里还见过有人把前缀和存成intN超过10^5就溢出定位异常难查。建议统一用long long特别是在跳跃优化里res和jump相乘那一步最容易溢出。5.4 m远大于n时的处理很多人写递推时直接res (res m) % i当m远大于n时每一轮都要做一次大数取模。取模本身是O(1)的问题不大但如果n很大且m也很大跳跃优化就用不上了因为res m i的条件几乎不成立。这时候还有个细节step要先对当前环规模取模。因为数M步和数M mod i步效果完全一样。我见过有人在递推里忘了这步导致M10^9时虽然能出正确结果但代码在跳跃优化里永远跳不动性能优化形同虚设。先把M规约到小于当前规模再判断能不能跳跃顺序不能反。5.5 方向转换时的镜像排名误区最后单独说双向剔除的镜像排名。很多人会写成“逆时针报数M步等效于顺时针报数(t-M)步”这个说法本身没错但忽略了一个关键起点是否被计算在内。我们假设起点是当前活人报数从起点的下一个开始数第1个。顺时针数M步出圈等价于从起点出发顺时针跳过M个人。逆时针数M步等价于顺时针跳过t - M个人因为逆向越过M个人后到达的位置恰好是正向从起点数第t-M个。这个换算需要仔细画图验证。我每次写都会在纸上画一个6人圈的样例手动模拟一遍再写代码。这不是浪费时间这种边界细节一旦错了小数据测试根本测不出来必须靠样例验证。6. 从一道题到一类题约瑟夫问题的思想扩展刷完这一圈之后我对“约瑟夫问题升级版”有一个很深的体会它考验的其实不是你会不会背那个递推公式而是你有没有一套“从模拟到数学、从暴力到数据结构”的思维阶梯。我能感受到的最有价值的思维方式是这样的——拿到一个变体题先问自己四个问题N有多大M是固定还是动态方向变不变要输出最终幸存者还是完整出圈过程这四个问题的答案组合在一起基本就能锁定解法区间。N很小就大胆模拟N很大就找数学规律要输出过程就上树状数组方向变化就做镜像转换。先做问题分类再动笔写代码是效率最高的路径。我还想提醒一点树状数组那个版本虽然叫“第四层”但在真实工程里其实比数学递推更常用。因为现实世界的问题往往规模不大但你需要完整追踪每一个出圈或淘汰的节点比如游戏匹配系统、任务调度里的轮询剔除、缓存淘汰策略的某些变体这类场景的核心逻辑都长得很像约瑟夫问题。有人问我为什么要写这么细我的回答是面试里算法题可以靠套路但工程里你要能基于这些问题形态做出正确的方案选型那才是更值钱的能力。最后分享一个实操习惯任何约瑟夫问题的代码我都建议先写一个N小、M固定的暴力版本生成正确答案然后再套用于优化版本做对拍。我每次调整方向转换逻辑或者跳跃优化时都靠这个对拍脚本兜底。如果你正在被某个升级版卡住不妨也先用最笨的模拟把答案跑出来再逐步优化这样既有参照物又能确认每一步的推导是否正确。