|
引言：一个有趣的儿童游戏每年六一儿童节，牛客网都会组织小朋友们玩一个特别的游戏：n个小朋友围成一圈，从编号0开始报数，数到m-1的小朋友出列并获得礼物，然后从下一位重新报数，直到剩下**一位幸运儿。这个看似简单的游戏背后，隐藏着计算机科学中**的约瑟夫环问题。 一、问题定义与暴力解法1.问题描述给定n个排成圆圈的人（编号0到n-1）和一个数字m，从第0人开始报数，每数到第m个人就将其淘汰，求**剩下的人的初始编号。 2.暴力模拟法最直观的解法是模拟整个过程： int lastRemaining(int n, int m) { vector<bool> out(n, false); // 标记是否出局 int current = 0; // 当前报数位置 int remain = n; // 剩余人数 while (remain > 1) { int count = 0; while (count < m) { if (!out[current]) { count++; } current = (current + 1) % n; } out[(current - 1 + n) % n] = true; remain--; } for (int i = 0; i < n; ++i) { if (!out) return i; } return -1;}时间复杂度分析：O(nm)，当n和m都很大时效率极低 3.数学递推解法约瑟夫环问题有一个优美的数学解法。设f(n,m)表示n个人报数m时的解： 递推过程解析这个公式的直观理解是：当一个人被淘汰后，问题规模缩小为n-1，新的起点是被淘汰者的下一位。我们需要将n-1的解映射回原始编号。 示例演算（n=5，m=3）： f(1,3)=0 f(2,3)=(f(1,3)+3)%2=(0+3)%2=1 f(3,3)=(f(2,3)+3)%3=(1+3)%3=1 f(4,3)=(f(3,3)+3)%4=(1+3)%4=0 f(5,3)=(f(4,3)+3)%5=(0+3)%5=3
高效实现基于递推公式的解法： int lastRemaining(int n, int m) { if (n < 1 || m < 1) return -1; int last = 0; // f(1,m)=0 for (int i = 2; i <= n; ++i) { last = (last + m) % i; } return last;}复杂度分析： 二、算法优化与变种优化方向变种问题双向约瑟夫环（顺时针和逆时针交替） 每次m变化的约瑟夫问题 找出淘汰顺序而不仅是**幸存者
三、完整代码：
C++
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param n int整型 * @param m int整型 * @return int整型 */ int LastRemaining_Solution(int n, int m) { if (n < 1 || m < 1) return -1; // 处理非法输入 int last = 0; // n=1时的解 // 递推公式：f(n,m)=(f(n-1,m)+m)%n for (int i = 2; i <= n; ++i) { last = (last + m) % i; } return last; // 返回**剩下的数字 }};四、总结从暴力模拟到数学递推，约瑟夫环问题展示了算法优化的重要性。理解这个问题的数学本质，不仅能解决具体编程问题，更能培养抽象思维和数学建模能力。记住这个优雅的递推公式：f(n,m)=(f(n-1,m)+m)%n，它将O(nm)的时间复杂度优化到了O(n)。 来源：牛客题解
| 
发表于