牛客网3704题：解密约瑟夫环

引言：一个有趣的儿童游戏

每年六一儿童节，牛客网都会组织小朋友们玩一个特别的游戏：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[i]) return i;
    }    return -1;
}

‌时间复杂度分析‌：O(nm)，当n和m都很大时效率极低

3.数学递推解法

约瑟夫环问题有一个优美的数学解法。设f(n,m)表示n个人报数m时的解：

1. 当n=1时，f(1,m)=0（只有一个人）

2. 对于n>1，f(n,m)=(f(n-1,m)+m)%n

递推过程解析

这个公式的直观理解是：当一个人被淘汰后，问题规模缩小为n-1，新的起点是被淘汰者的下一位。我们需要将n-1的解映射回原始编号。

‌示例演算‌（n=5，m=3）：

1. f(1,3)=0

2. f(2,3)=(f(1,3)+3)%2=(0+3)%2=1

3. f(3,3)=(f(2,3)+3)%3=(1+3)%3=1

4. f(4,3)=(f(3,3)+3)%4=(1+3)%4=0

5. 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;
}

‌复杂度分析‌：

• 时间复杂度：O(n)

• 空间复杂度：O(1)

二、算法优化与变种

优化方向

1. 当m远大于n时，可以先计算m%n减少迭代次数

2. 对于超大n的情况，可以寻找数学规律进一步优化

变种问题

1. 双向约瑟夫环（顺时针和逆时针交替）

2. 每次m变化的约瑟夫问题

3. 找出淘汰顺序而不仅是最后幸存者

三、完整代码：

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)。