循环数组通过取模运算模拟约瑟夫环,用一维数组存编号、布尔数组标记淘汰状态,指针cur=(cur+1)%n自动回卷,仅对未淘汰者计数,淘汰时执行记录编号、标记、减幸存数、清计数四步闭环。

循环数组是模拟约瑟夫环最直观、低门槛的实现方式,关键在于用取模运算(%)代替物理“绕圈”,让索引自动回卷,避免边界判断出错。
用一维数组建环,状态标记要清晰
不需要真的构造链表或移动元素,只需一个长度为 n 的数组存储编号(如 people[0] = 1, people[1] = 2, ..., people[n-1] = n),再配一个等长布尔数组(或整型标记数组)表示是否已淘汰。标记为 false 或 0 表示在圈内,true 或 1 表示已出列。这样每次访问都通过合法下标进行,逻辑干净。
- 初始化时顺序填入 1 到 n,淘汰标记全设为未淘汰
- 报数过程只在“未淘汰”位置上累加计数,跳过已淘汰者
- 淘汰一人后不删除数组元素,仅改标记——节省时间,也便于后续定位原始编号
指针推进靠取模,避免手动重置
当前下标用变量 cur 表示,每轮检查下一个人时执行 cur = (cur + 1) % n。这个操作天然实现“走到末尾自动回到开头”,无需 if 判断是否越界。配合淘汰标记,就能在逻辑环中持续行走。
- 例如 n=5,当前在索引 4(即第5人),
(4 + 1) % 5 = 0,自然跳到索引 0(第1人) - 若中间有人已淘汰,就继续
cur = (cur + 1) % n直到遇到下一个未淘汰者 - 报数计数器(step)只在碰到未淘汰者时才 +1,确保“数的是活人”
淘汰动作四步闭环,顺序不能乱
一旦 step 达到 m,立刻执行淘汰:记录此人编号 → 标记为已淘汰 → 幸存人数减 1 → 计数器归零。这四步构成一个原子操作,缺一不可,否则会导致重复计数或漏淘汰。
- 记录编号用于输出淘汰序列,对调试和验证至关重要
- 标记必须立即生效,否则下次行走可能再次计入此人
- 幸存人数(alive)用于控制 while 循环终止条件:
while (alive > 1)或while (len(result) - 计数器归零保证下一轮从 1 重新开始报数
定位最后幸存者,别依赖遍历查找
当只剩一人时,不必遍历整个数组找唯一未淘汰项。可在每轮淘汰后实时维护一个“当前起始有效位置”,或更简单:在循环结束前,用一个变量持续追踪最后一个被淘汰者的下一个未淘汰者——它就是最终幸存者。但最稳妥的做法仍是循环结束后扫描一次标记数组,找到那个 eliminated[i] == false 的 i,返回 people[i]。
- 注意编号偏移:数组索引从 0 开始,人编号从 1 开始,输出时别忘了 +1
- 若需输出完整淘汰顺序,把每次淘汰的
people[i]按序存入列表即可 - 该方法时间复杂度 O(n×m),适合 n ≤ 10⁴ 场景;更大规模建议切换递推公式










