阿里 约瑟夫环问题

题目要求：实现一个约瑟夫环（Josephus problem）：N个人围成一圈，从第一个人开始按顺序报数，每数到第M个人就把他淘汰（出局），然后从下一个人重新报数。如此重复，直到只剩最后一个人。请问最后剩下的人最初在什么位置（或编号）？

举例：

例1：N=5，M=2
圆圈：1，2，3，4，5

• 从1数，2出局，剩下：1，3，4，5（从3开始）

• 数到4出局，剩下：1，3，5（从5开始）

• 数到1出局，剩下：3，5（从3开始）

• 数到5出局，剩下：3 ✅（幸存者是3号）

例2：N=7，M=3 → 最后幸存者是4号。

一、模拟法：

1.思路：模拟约瑟夫环逐个淘汰的过程。

（1）初始时有n个人，全部未出局。

（2）循环直到只剩一人：

（a）移动到下一个人（如果循环到第n个后需要回到第1个）。

（b）如果这个人未出局，报数+1。

（c）如果报数达到m：标记此人出局，打印出局信息，重置报数计数器为0，将剩余人数 - 1。

（3）遍历查找唯一的未出局者，返回其编号。

2.复杂度分析：

（1）时间复杂度：O(n × m)，需要淘汰n - 1个人，每淘汰一个人都要检查m个元素，当n较大时效率低。当m接近于n时，时间复杂度最坏可达到O(n^2)。

（2）空间复杂度：O(n)。额外需要一个boolean数组存储当前位是否已经淘汰。

附代码：

class Solution { public int josephus(int n, int m) { // 使用数组标记是否出局 boolean[] out = new boolean[n + 1]; // 1-indexed，下标0不用 int count = n; // 剩余人数 int i = 0; // 当前位置 int step = 0; // 已报数步数 while (count > 1) { i++; if (i > n) i = 1; if (!out[i]) { step++; if (step == m) { out[i] = true; System.out.printf("出局: %d\n", i); step = 0; count--; } } } // 找出幸存者 for (i = 1; i <= n; i++) { if (!out[i]) return i; } return -1; } }

ACM模式：

import java.util.Scanner; class Solution { public int josephus(int n, int m) { // 使用数组标记是否出局 boolean[] out = new boolean[n + 1]; // 1-indexed，下标0不用 int count = n; // 剩余人数 int i = 0; // 当前位置 int step = 0; // 已报数步数 while (count > 1) { i++; if (i > n) i = 1; if (!out[i]) { step++; if (step == m) { out[i] = true; System.out.printf("出局: %d\n", i); step = 0; count--; } } } // 找出幸存者 for (i = 1; i <= n; i++) { if (!out[i]) return i; } return -1; } } public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int m = scanner.nextInt(); Solution solution = new Solution(); int survivor = solution.josephus(n, m); System.out.println("幸存者: " + survivor); scanner.close(); } }

二、递推公式法（最优解）：

1.思路：不模拟淘汰过程，而是反向推导：已知1个人时的幸存者位置，推出第2个人、3个人......直到n个人时的幸存者位置。

2.递推公式：

f(1) = 0 // 只有1个人时，幸存者索引是0（0-indexed）
f(n) = (f(n-1) + m) % n // 增加第n个人后，新幸存者索引的计算公式

对应代码实现：

for (int i = 2; i <= n; i++) { // 从2个人开始递推，直到n个人 survivor = (survivor + m) % i; // 核心递推公式 }

3.公式解释：

（1）假设已知n - 1个人的时候，幸存者索引为f(n - 1)，它是在旧圈中的位置。

（2）当人数从n - 1增加到n时，相当于在圆圈中插入了一个新的人（编号0）。

（3）报数时会跳过m个人，所以新幸存者的索引要在旧索引的基础上向后移动m步。

（4）再对当前人数n取模（因为是圆圈结构）。

4.复杂度分析：

（1）时间复杂度：O(n)，只需要1次循环。

（2）空间复杂度：O(1)，只需要一个变量survivor。

附代码：

class Solution { public int josephus(int n, int m) { if (n <= 0 || m <= 0) return -1; // 参数合法性检查 int survivor = 0; // 初始：f(1) = 0（n = 1时，幸存者在第0个位置） for (int i = 2; i <= n; i++) { // 从2个人开始递推，直到n个人 survivor = (survivor + m) % i; // 核心递推公式 } // 这个代码只能拿到最终的幸存者编号，无法拿到每轮出局的人是谁 return survivor + 1; // 题目通常要求1-indexed（编号从1开始） } }

ACM模式：

import java.util.Scanner; class Solution { public int josephus(int n, int m) { if (n <= 0 || m <= 0) return -1; // 参数合法性检查 int survivor = 0; // 初始：f(1) = 0（n = 1时，幸存者在第0个位置） for (int i = 2; i <= n; i++) { // 从2个人开始递推，直到n个人 survivor = (survivor + m) % i; // 核心递推公式 } // 这个代码只能拿到最终的幸存者编号，无法拿到每轮出局的人是谁 return survivor + 1; // 题目通常要求1-indexed（编号从1开始） } } public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int m = scanner.nextInt(); Solution solution = new Solution(); int survivor = solution.josephus(n, m); System.out.println("幸存者: " + survivor); scanner.close(); } }