1823.找出游戏的获胜者

题目

找出游戏的获胜者

思路

使用队列将所有数字存储起来，然后进行循环遍历直到队列中只剩一个元素，每次循环先将 k 减一，将队头元素使用临时变量保存起来，然后出队，dang k 不等于0时，将刚出队的元素再次入队，若 k 等于0，则需要更新 k 。

题解

• 题解1

class Solution {
public:
    int findTheWinner(int n, int k) {
        queue<int> que;
        for(int i = 1; i <= n; i ++){
            que.push(i);
        }
        int x = k;
        while(que.size() > 1){  // 循环遍历，直到队列中只剩一人
            x --;
            int top = que.front();
            que.pop();
            if(x != 0){  // 当还没到第k个，则再次入栈
                que.push(top);
            }
            else{  // 到第k个，则需要更新x，再次计数
                x = k;
            }
        }
        return que.front();
    }
};

• 时间复杂度：O(n \ k)，其中 n 是做游戏的小伙伴数量，k 是每一轮离开圈子的小伙伴的计数。初始时需要将 n 个元素加入队列，每一轮需要将 k 个元素从队列中取出，将 k−1 个元素加入队列，一共有 n−1 轮，因此时间复杂度是 O(n * k)*。
• 空间复杂度：O(n)，队列最多有n个元素。

执行用时：72 ms, 在所有 C++ 提交中击败了11.70%的用户

内存消耗：23.8 MB, 在所有 C++ 提交中击败了15.31%的用户

通过测试用例：95 / 95