牛客3407题解：用递推破解约瑟夫环

一、题目解读

牛客3407题（约瑟夫环问题）要求n个人围成环，从第1个人开始报数，报到m的人出列，重复直至剩最后一人。用户提供的代码通过递推公式直接计算最后幸存者的编号，避免了传统环形链表模拟的高复杂度，实现高效求解。

二、解题思路

核心思想为：

1. 数学建模：将问题转化为递推关系，利用数学归纳法推导公式；

2. 递推公式：定义f(n,m)为n人环中最后幸存者编号，则f(n,m) = (f(n-1,m) + m) % n；

3. 边界条件：当n=1时，唯一幸存者编号为0（即第1人），递推由此展开；

4. 优化逻辑：通过取模运算避免数组模拟，直接计算最终结果。

三、解题步骤

1. 输入校验：若n或m非法（<1），返回-1；

2. 初始化：设置last=0（即f(1,m)=0）；

3. 递推循环：从i=2到n，执行last = (last + m) % i，模拟人数递增时的幸存者编号变化；

4. 结果返回：循环结束后，last即为最终答案。

四、代码与注释

class Solution {
public:
    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; // 返回最后剩下的数字
    }
};

五、总结

本解法通过递推公式将复杂的环形淘汰问题转化为线性计算，时间复杂度O(n)，空间复杂度O(1)。关键在于理解递推关系的数学本质，避免传统模拟带来的高开销。适用于需要高效求解约瑟夫环问题的场景，展示了算法设计中“化繁为简”的巧妙思路。