算法题剖析：找出游戏的获胜者（二）

接上文，我们来讲讲解决方案

方法一：模拟 + 队列

思路和算法

最直观的方法是模拟游戏过程。使用队列存储圈子中的小伙伴编号，初始时将 1 到 n 的所有编号依次加入队列，队首元素即为第 1 名小伙伴的编号。

每一轮游戏中，从当前小伙伴开始数 k 名小伙伴，数到的第 k 名小伙伴离开圈子。模拟游戏过程的做法是，将队首元素取出并将该元素在队尾处重新加入队列，重复该操作 k-1 次，则在 k−1 次操作之后，队首元素即为这一轮中数到的第 k 名小伙伴的编号，将队首元素取出，即为数到的第 k 名小伙伴离开圈子。上述操作之后，新的队首元素即为下一轮游戏的起始小伙伴的编号。

每一轮游戏之后，圈子中减少一名小伙伴，队列中减少一个元素。重复上述过程，直到队列中只剩下 1 个元素，该元素即为获胜的小伙伴的编号。

代码

Python3

class Solution: def findTheWinner(self, n: int, k: int) -> int: q = deque(range(1, n + 1)) while len(q) > 1: for _ in range(k - 1): q.append(q.popleft()) q.popleft() return q[0]

Java

class Solution { public int findTheWinner(int n, int k) { Queue<Integer> queue = new ArrayDeque<Integer>(); for (int i = 1; i <= n; i++) { queue.offer(i); } while (queue.size() > 1) { for (int i = 1; i < k; i++) { queue.offer(queue.poll()); } queue.poll(); } return queue.peek(); } }

C#

public class Solution { public int FindTheWinner(int n, int k) { Queue<int> queue = new Queue<int>(); for (int i = 1; i <= n; i++) { queue.Enqueue(i); } while (queue.Count > 1) { for (int i = 1; i < k; i++) { queue.Enqueue(queue.Dequeue()); } queue.Dequeue(); } return queue.Peek(); } }

C++

class Solution { public: int findTheWinner(int n, int k) { queue<int> qu; for (int i = 1; i <= n; i++) { qu.emplace(i); } while (qu.size() > 1) { for (int i = 1; i < k; i++) { qu.emplace(qu.front()); qu.pop(); } qu.pop(); } return qu.front(); } };

复杂度分析

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

空间复杂度：O(n)，其中 n 是做游戏的小伙伴数量。空间复杂度主要取决于队列，队列中最多有 n 个元素。