2023年8月16日每日一题--2682. 找出转圈游戏输家

leetcode链接：2682. 找出转圈游戏输家

题目分析

方案一

用一个数组来判断那个孩子被选中了，那个孩子没有被选中。

最终结果根据上个选择数据去生成

class Solution {  
    public int[] circularGameLosers(int n, int k) {  
  
        boolean[] children = new boolean[n];  
        int sum = 1, index = 0, kNum = k;  
        children[0] = true;  
  
        while (true) {  
            index = (index + kNum) % n;  
            if (children[index]) break;  
            kNum += k;  
            sum++;  
            children[index] = true;  
        }  
  
        int[] result = new int[n - sum];  
        index = 0;  
        for (int i = 0; i < n - sum;) {  
            if (!children[index]) {  
                result[i] = index + 1;  
                i++;  
            }  
            index++;  
        }  
  
        return result;  
    }  
}

结果

解答成功:
执行耗时:1 ms,击败了100.00% 的Java用户
内存消耗:42.5 MB,击败了90.95% 的Java用户

分析

时间复杂度：
O( n )

空间复杂度：
O( n )

官方题解

https://leetcode.cn/problems/find-the-losers-of-the-circular-game/solutions/2387382/zhao-chu-zhuan-quan-you-xi-shu-jia-by-le-rfiq/

方法一：直接模拟

class Solution {
    public int[] circularGameLosers(int n, int k) {
        boolean[] visit = new boolean[n];
        for (int i = k, j = 0; !visit[j]; i += k) {
            visit[j] = true;
            j = (j + i) % n;
        }
        List<Integer> list = new ArrayList<Integer>();
        for (int i = 0; i < n; i++) {
            if (!visit[i]) {
                list.add(i + 1);
            }
        }
        int[] ans = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            ans[i] = list.get(i);
        }
        return ans;
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/find-the-losers-of-the-circular-game/solutions/2387382/zhao-chu-zhuan-quan-you-xi-shu-jia-by-le-rfiq/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。