找出转圈游戏输家【LC2682】
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 作为答案。
昨天梦到面试在手撕一道很有意思的算法，还没手撕出来呢，就醒了，醒来题目也忘了，难受
思路：哈希表+模拟
使用哈希表记录每个位置的访问状态，进行模拟直至一个位置被重复访问。模拟过程中记录访问的轮次，剩余人数即为n − i n-in−i，再次遍历哈希表，将未访问过的位置按照从小到大的顺序放入结果中
实现
class Solution { public int[] circularGameLosers(int n, int k) { boolean[] vis = new boolean[n]; vis[0] = true; int index = 0, i = 1; while(true){ index = (index + i * k) % n; if (vis[index]){ break; } i++; vis[index] = true; } int[] res = new int[n - i]; i = 0; for (int j = 0; j < n; j++){ if (!vis[j]){ res[i++] = j + 1; } } return res; } }
复杂度
时间复杂度：O ( n )
空间复杂度：O ( n )
