阿里 约瑟夫环问题

题目要求实现一个约瑟夫环Josephus problemN个人围成一圈从第一个人开始按顺序报数每数到第M个人就把他淘汰出局然后从下一个人重新报数。如此重复直到只剩最后一个人。请问最后剩下的人最初在什么位置或编号举例例1N5M2圆圈12345从1数2出局剩下1345从3开始数到4出局剩下135从5开始数到1出局剩下35从3开始数到5出局剩下3 ✅幸存者是3号例2N7M3 → 最后幸存者是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个人时幸存者索引是00-indexedf(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) 0n 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) 0n 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(); } }