LCR 187. 破冰游戏 (opens new window)

题目：

社团共有 num 为成员参与破冰游戏，编号为 0 ~ num-1。成员们按照编号顺序围绕圆桌而坐。社长抽取一个数字 target，从 0 号成员起开始计数，排在第 target 位的成员离开圆桌，且成员离开后从下一个成员开始计数。请返回游戏结束时最后一位成员的编号。

示例：

示例 1：

输入：num = 7, target = 4
输出：1

示例 2：

输入：num = 12, target = 5
输出：0

提示：

• 1 <= num <= 10^5
• 1 <= target <= 10^6

解题:

方法一：迭代法

这是一个经典的约瑟夫环问题。可以使用递归或迭代来解决。

思路：

1. 这种解法使用迭代的方式模拟约瑟夫环的过程。假设删除的位置为 last，当前数组长度为 n。

2. 初始时，我们设置 last = 0，表示从 0 号位置开始。然后，我们循环从 2 号位置（数组长度为2）到 n 号位置（数组长度为 n），更新 last 的位置。

3. 具体的更新公式是 last = (last + m) % i，其中 i 表示当前的数组长度。

4. 这个公式的意义是，每次删除一个数字后，我们从下一个数字开始重新计数，并在新的数组长度下更新当前位置。

5. 最终，留下的 last 就是游戏结束时最后一位成员的编号。

last = (last + m) % i是怎么来的？

这个更新公式是模拟在当前数组长度为 i 时，每次删除一个数字后，下一个数字的位置。

让我们逐步解释这个公式：

• last: 表示当前删除数字的位置。
• m: 表示社长抽取的数字 target。
• i: 表示当前成员数组的长度。

每次删除一个数字后，我们从下一个数字开始重新计数。为了找到下一个数字的位置，我们将当前位置 last 加上 m，表示我们向后移动了 m 个位置。然后，我们取这个移动后的位置对当前数组长度 i 取模，确保我们不越界。这样，得到的新的 last 就是下一轮的起始位置。

这个操作模拟了游戏中的计数过程，每次删除一个数字后，从下一个数字重新开始计数。这个公式在约瑟夫环的问题中经常用到。

class Solution {
public:
    int lastRemaining(int n, int m) {
        int last = 0;
        for (int i = 2; i <= n; i++) {
            last = (last + m) % i;
        }
        return last;
    }
};
/*
 在这个算法中，i 表示当前的成员数量。
 循环从 i = 2 开始，是因为对于 i = 1 的情况，即只有一个成员的情况，这个成员就是最后留下的，无需进行循环计算。
 因此，从 i = 2 开始，依次计算每次抽取一个成员后剩余成员的最后一个留下的编号。
*/ 

复杂度：

• 时间复杂度是 O(n)
• 空间复杂度是 O(1)