2682. 找出转圈游戏输家

难度: 简单

来源: 每日一题 2023.08.16

---

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

class Solution {
    public int[] circularGameLosers(int n, int k) {

    }
}

分析与题解

---

• HashMap

  对于这个题目, 我整体的思路是这样的, 我们下标都存到一个 Set集合 中, 然后模拟游戏过程, 当遇到在 Set集合 中的元素就删除掉, 如果 Set集合 没有该元素说明先前已经删除了, 这时候就停止游戏.

  首先, 我们先进行 Set集合 的构建, 过程如下所示.

  Set<Integer> cache = new HashSet<Integer>();
  for(int i = 0; i < n; i++) {
      cache.add(i);
  }
  

  然后, 我们要通过模拟法查找游戏当前的下标, 并且从 Set集合 删除. 同时, 查找下一个下标, 查找下一个下标, 我们可以利用 对 n 取余 直接得出下一个下标的位置.

  Integer start = 0;
  int count = 1;
  while(cache.contains(start)) {
      cache.remove(start);
      start += count * k;
      start = start%n;
      count++;
  }
  

  最后一步, 构建我们的结果数组即可.

  int[] result = new int[cache.size()];
  int index = 0;
  for(Integer item: cache) {
      result[index] = (item + 1);
      index++;
  }
  Arrays.sort(result);
  

  整体逻辑代码如下所示.

  class Solution {
      public int[] circularGameLosers(int n, int k) {
          Set<Integer> cache = new HashSet<Integer>();
          for(int i = 0; i < n; i++) {
              cache.add(i);
          }
          Integer start = 0;
          int count = 1;
          while(cache.contains(start)) {
              cache.remove(start);
              start += count * k;
              start = start%n;
              count++;
          }
          int[] result = new int[cache.size()];
          int index = 0;
          for(Integer item: cache) {
              result[index] = (item + 1);
              index++;
          }
          Arrays.sort(result);
          return result;
  
      }
  }
  

  复杂度分析:

  • 时间复杂度: O(2n), 遍历添加到Set中是 O(n), 寻找下一位以及构建结果数组是 O(n).
  • 空间复杂度: O(n), 需要构建长度为 n 的 Set集合空间.

  结果如下所示.

  

• 优化

  主要的优化点是由 先添加再删除 变为 往Set内部添加数据, 这样,时间复杂度会进一步的降低.

  class Solution {
      public int[] circularGameLosers(int n, int k) {
          Set<Integer> cache = new HashSet<Integer>();
          Integer start = 0;
          int count = 1;
          while(!cache.contains(start)) {
              cache.add(start);
              start += count * k;
              start = start%n;
              count++;
          }
          int[] result = new int[n - cache.size()];
          int index = 0;
          for(int i = 0; i < n; i++) {
              if (!cache.contains(i)) {
                  result[index] = (i + 1);
                  index++;
              }
          }
          return result;
  
      }
  }
  

  复杂度分析:

  • 时间复杂度: O(cache.lenght + n), 添加到Set中是 O(cache.lenght), 构建结果数组是 O(n).
  • 空间复杂度: O(cache.lenght), 需要构建长度为 cache.lenght 的 Set集合空间.

  结果如下所示.