Easy

题目描述

有 n 个朋友在玩一个游戏。这些朋友坐成一个圆圈，按顺时针方向编号从 1 到 n。更正式地说，从第 i 个朋友顺时针移动会到达第 (i+1) 个朋友（对于 1 <= i < n），从第 n 个朋友顺时针移动会到达第 1 个朋友。

游戏规则如下：

  • 第 1 个朋友接收球。
  • 然后，第 1 个朋友将球传给距离他们顺时针方向 k 步的朋友。
  • 接下来，接收球的朋友应该将球传给距离他们顺时针方向 2 * k 步的朋友。
  • 然后，接收球的朋友应该将球传给距离他们顺时针方向 3 * k 步的朋友，依此类推。

换句话说，在第 i 轮中，持球的朋友应该将球传给距离他们顺时针方向 i * k 步的朋友。

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

游戏的失败者是在整个游戏中没有接收过球的朋友。

给定朋友数量 n 和整数 k，返回包含游戏失败者的数组 answer，按升序排列。

示例 1：

输入：n = 5, k = 2
输出：[4,5]
解释：游戏过程如下：
1) 从第 1 个朋友开始，将球传给距离 2 步的朋友 - 第 3 个朋友。
2) 第 3 个朋友将球传给距离 4 步的朋友 - 第 2 个朋友。
3) 第 2 个朋友将球传给距离 6 步的朋友 - 第 3 个朋友。
4) 游戏结束，因为第 3 个朋友第二次接收球。

示例 2：

输入：n = 4, k = 4
输出：[2,3,4]
解释：游戏过程如下：
1) 从第 1 个朋友开始，将球传给距离 4 步的朋友 - 第 1 个朋友。
2) 游戏结束，因为第 1 个朋友第二次接收球。

约束：

  • 1 <= k <= n <= 50

解题思路

解题思路

这是一道模拟题，我们需要按照游戏规则模拟整个传球过程，直到某个朋友第二次接收球为止。

核心思路：

  1. 使用集合（或布尔数组）记录每个朋友是否接收过球
  2. 从第1个朋友开始，按照游戏规则依次传球
  3. 在第i轮传球时，传球距离为 i * k 步
  4. 使用取模运算处理环形结构：(当前位置 + 步数 - 1) % n + 1
  5. 当某个朋友第二次接收球时结束游戏
  6. 找出所有未接收过球的朋友

算法步骤：

  • 初始化访问记录，当前位置为1（第1个朋友）
  • 循环模拟传球过程：
    • 记录当前朋友接收球
    • 如果该朋友已经接收过球，游戏结束
    • 否则计算下一个接收球的朋友位置
  • 遍历所有朋友，收集未接收过球的朋友编号

推荐解法： 使用哈希集合记录接收过球的朋友，时间复杂度最优。

代码实现

class Solution {
public:
    vector<int> circularGameLosers(int n, int k) {
        unordered_set<int> received;
        int current = 1;
        int turn = 1;
        
        while (received.find(current) == received.end()) {
            received.insert(current);
            current = (current + (long long)turn * k - 1) % n + 1;
            turn++;
        }
        
        vector<int> result;
        for (int i = 1; i <= n; i++) {
            if (received.find(i) == received.end()) {
                result.push_back(i);
            }
        }
        
        return result;
    }
};

class Solution:
    def circularGameLosers(self, n: int, k: int) -> List[int]:
        received = set()
        current = 1
        turn = 1
        
        while current not in received:
            received.add(current)
            current = (current + turn * k - 1) % n + 1
            turn += 1
        
        return [i for i in range(1, n + 1) if i not in received]

public class Solution {
    public int[] CircularGameLosers(int n, int k) {
        HashSet<int> received = new HashSet<int>();
        int current = 1;
        int turn = 1;
        
        while (!received.Contains(current)) {
            received.Add(current);
            current = (current + (long)turn * k - 1) % n + 1;
            turn++;
        }
        
        List<int> result = new List<int>();
        for (int i = 1; i <= n; i++) {
            if (!received.Contains(i)) {
                result.Add(i);
            }
        }
        
        return result.ToArray();
    }
}

var circularGameLosers = function(n, k) {
    const received = new Set();
    let current = 1;
    let turn = 1;
    
    while (!received.has(current)) {
        received.add(current);
        current = (current + turn * k - 1) % n + 1;
        turn++;
    }
    
    const result = [];
    for (let i = 1; i <= n; i++) {
        if (!received.has(i)) {
            result.push(i);
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)最坏情况下需要访问所有朋友才结束游戏
空间复杂度O(n)使用哈希集合存储接收过球的朋友，最多存储n个元素

相关题目