找出转圈游戏输家

难度: Easy

n 个朋友在玩游戏。这些朋友坐成一个圈，按 顺时针方向 从 1 到 n 编号。准确的说，从第 i 个朋友的位置开始顺时针移动 1 步会到达第 (i + 1) 个朋友的位置（1 <= i < n），而从第 n 个朋友的位置开始顺时针移动 1 步会回到第 1 个朋友的位置。

游戏规则如下：

第 1 个朋友接球。

接着，第 1 个朋友将球传给距离他顺时针方向 k 步的朋友。
然后，接球的朋友应该把球传给距离他顺时针方向 2 * k 步的朋友。
接着，接球的朋友应该把球传给距离他顺时针方向 3 * k 步的朋友，以此类推。

换句话说，在第 i 轮中持有球的那位朋友需要将球传递给距离他顺时针方向 i * k 步的朋友。

当某个朋友第 2 次接到球时，游戏结束。

在整场游戏中没有接到过球的朋友是输家。

给你参与游戏的朋友数量 n 和一个整数 k ，请按升序排列返回包含所有输家编号的数组 answer 作为答案。

示例 1：

输入：n = 5, k = 2
输出：[4,5]
解释：以下为游戏进行情况：
1）第 1 个朋友接球，第 1 个朋友将球传给距离他顺时针方向 2 步的玩家 —— 第 3 个朋友。
2）第 3 个朋友将球传给距离他顺时针方向 4 步的玩家 —— 第 2 个朋友。
3）第 2 个朋友将球传给距离他顺时针方向 6 步的玩家 —— 第 3 个朋友。
4）第 3 个朋友接到两次球，游戏结束。

示例 2：

输入：n = 4, k = 4
输出：[2,3,4]
解释：以下为游戏进行情况：
1）第 1 个朋友接球，第 1 个朋友将球传给距离他顺时针方向 4 步的玩家 —— 第 1 个朋友。
2）第 1 个朋友接到两次球，游戏结束。

提示：

1 <= k <= n <= 50

Submission

运行时间: 28 ms

内存: 16.7 MB

class Solution:
    def circularGameLosers(self, n: int, k: int) -> List[int]:
        friend = [False] * n
        friend[0] = True
        i = 1
        temp = 0
        result = []
        while True:
            temp += i * k
            temp %= n
            if friend[temp] and i != 1: break
            friend[temp] = True
            i += 1
        for i in range(n):
            if not friend[i]:
                result.append(i+1)
        return result

Explain

此题解采用模拟的方式来跟踪球的传递过程。首先，初始化一个布尔数组 `friend` 来标记每个朋友是否接过球。数组的索引表示朋友的编号（从0开始，即编号1的朋友是 `friend[0]`）。游戏从第1个朋友开始，因此 `friend[0]` 初始化为 `True`。随后，使用变量 `temp` 来记录当前持球者的位置，并用变量 `i` 来记录传球的轮次。游戏继续进行，直到一个朋友第二次接到球，此时游戏结束。最后，遍历 `friend` 数组，将未接过球的朋友编号（加1后）添加到结果列表 `result` 中。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def circularGameLosers(self, n: int, k: int) -> List[int]:
        friend = [False] * n  # 初始化数组，用于标记是否接过球
        friend[0] = True  # 第1个朋友开始接球
        i = 1  # 从第1轮开始
        temp = 0  # 当前持球者的位置（从0开始）
        result = []  # 存储没有接到球的朋友的编号
        while True:
            temp += i * k  # 计算新的接球者位置
            temp %= n  # 保证位置在0到n-1的范围内
            if friend[temp] and i != 1: break  # 如果这个朋友已经接过球，且不是第1轮，则结束游戏
            friend[temp] = True  # 标记为接过球
            i += 1  # 增加轮次
        for i in range(n):
            if not friend[i]:
                result.append(i+1)  # 未接过球的朋友编号（需要加1）
        return result

Explore

在本题的模拟中，朋友的编号被直接映射到数组 `friend` 的索引上，其中朋友编号从1开始，但数组索引从0开始。因此，当我们引用 `friend[0]` 时，实际上是指的第1个朋友，`friend[1]` 是第2个朋友，依此类推。这种映射通过在数组操作时将朋友编号减去1来实现，从而确保每个朋友的编号正确地对应到数组索引上。

虽然`i * k`的结果随着游戏轮次的增加而快速增长，但在每次计算后立即使用`temp %= n`将其模上n（朋友总数），保证`temp`始终在合理范围内（0到n-1）。这样做有效避免了整数溢出的问题，并且由于`temp`的值始终受到n的限制，所以不会导致性能问题。

是的，根据题解逻辑，游戏将在某个朋友第二次接到球时立即结束。在游戏结束后，将会检查`friend`数组，列出所有值为假的索引，即那些未曾接到球的朋友。这些朋友的编号（索引+1）将被添加到结果列表`result`中，从而确保所有未参与接球的朋友都被正确处理。

这是基于游戏规则的假设和设计。题解中假设游戏始于第1个朋友接球，并且在第1轮中，`friend[0]` 被设置为 `True`。因为游戏需要在某人第二次接球时才结束，所以第1轮接球不会导致游戏结束。这个设定是为了确保游戏至少完整进行一轮，让每个朋友都有可能接到球。