题解 | #孩子们的游戏(圆圈中最后剩下的数)#
孩子们的游戏(圆圈中最后剩下的数)
https://www.nowcoder.com/practice/f78a359491e64a50bce2d89cff857eb6
/** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @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, };