一、题目描述

每年六一儿童节，牛客都会准备一些小礼物去看望孤儿院的小朋友。其中有个游戏规则如下：

1. 让小朋友们围成一个大圈，小朋友编号从0到n-1；
2. 随机指定一个数m，从编号为0的小朋友开始报数；
3. 每次喊到m-1的小朋友要出列唱首歌，然后不再回到圈中；
4. 从出列小朋友的下一个小朋友开始，继续按0...m-1的规则报数；
5. 重复上述过程，直到剩下最后一个小朋友，该小朋友可获得“名侦探柯南”典藏版礼品。

要求：求出最终获得礼品的小朋友编号。

二、解题思路

若仅需求最后一个报数胜利者的编号，可通过数学归纳法推导解决方案，具体分析如下：

1. 问题转换

将原问题抽象为数学模型：n个人（编号0~n-1）围成圈，从0开始报数，报到m-1的人退出，剩余的人继续从0报数，求最终胜利者的编号。

2. 子问题推导

当第一个人（编号为k = m % n - 1）出列后，剩余n-1人组成新的“约瑟夫环”，新环的起始编号为k + 1（即原编号k的下一个人），新环的编号序列为：
k, k+1, k+2, ..., n-2, n-1, 0, 1, 2, ..., k-2

为简化计算，对新环编号做映射转换，将其转化为n-1人游戏的标准模型（从0开始连续编号）：

新环原编号 映射后编号 k 0 k+1 1 k+2 2 ... ... k-2 n-2

3. 递推公式推导

设f[i]表示“i个人玩游戏，报m退出”场景下最终胜利者的编号，则：

• 边界条件：当只有1个人时（i=1），胜利者只有自己，即f[1] = 0；
• 递推关系：若已知i-1人游戏的胜利者编号为f[i-1]，则i人游戏的胜利者编号可通过映射逆运算得到，公式为：
  f[i] = (f[i-1] + m) % i（i>1）

三、C# 代码实现

public class Solution
{
    /// <summary>
    /// 求解圆圈中最后剩下的数（约瑟夫环问题）
    /// </summary>
    /// <param name="n">初始人数（编号0~n-1）</param>
    /// <param name="m">报数阈值（报到m-1的人出列）</param>
    /// <returns>最终胜利者的编号，若输入无效则返回-1</returns>
    public int LastRemaining_Solution(int n, int m)
    {
        // 输入合法性校验：人数n或报数阈值m小于1时，无有效结果
        if (n < 1 || m < 1)
        {
            return -1;
        }
        
        // 初始值：1人时胜利者编号为0
        int last = 0;
        
        // 从2人开始递推，直到计算出n人时的结果
        for (int i = 2; i <= n; i++)
        {
            last = (last + m) % i;
        }
        
        return last;
    }
}

代码说明

1. 输入校验：首先判断n和m是否为正整数，若存在非正整数则返回-1（无效场景）；
2. 初始值设定：last初始化为0，对应“1人游戏”的胜利者编号；
3. 循环递推：从2人游戏开始，通过公式(last + m) % i逐步计算每增加1人后的胜利者编号，最终得到n人游戏的结果；
4. 时间复杂度：O(n)，仅需一次循环遍历；
5. 空间复杂度：O(1)，仅使用常量级额外空间。