题解 | #孩子们的游戏(圆圈中最后剩下的数)#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param n int整型
 * @param m int整型
 * @return int整型
 */
function LastRemaining_Solution(n, m) {
    // 约瑟夫环数学解法，反推找规律
    // 数组后拼接数组模拟环
    // 最后只剩下一个元素，假设这个最后的元素为num, 那它的下标一定是0 （因为最后只剩这一个元素）
    // 所以如果我们可以推出上一轮次中这个num的下标，然后根据上一轮num的下标推断出上上一轮num的下标，直到推断出元素个数为n的那一轮num的下标，那我们就可以根据这个下标获取到最终的元素了。
    // 推断过程：
    // 最后一轮num下标肯定为0
    // 上一轮有两个元素，此轮num下标为(0 + m) % n，这个n是当前轮次数组的大小
    // 以此反推直到数组大小为n
    // 最后一轮num下标为0
    let res = 0;
    // 倒数第二轮只剩两个人，从该轮次开始反推num下标，直到第一轮（人数为n）
    for (let i = 2; i <= n; i++) {
        res = (res + m) % i;
    }
    return res;
}
module.exports = {
    LastRemaining_Solution: LastRemaining_Solution,
};