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

接上文我们来讲讲解决方案方法一模拟 队列思路和算法最直观的方法是模拟游戏过程。使用队列存储圈子中的小伙伴编号初始时将 1 到 n 的所有编号依次加入队列队首元素即为第 1 名小伙伴的编号。每一轮游戏中从当前小伙伴开始数 k 名小伙伴数到的第 k 名小伙伴离开圈子。模拟游戏过程的做法是将队首元素取出并将该元素在队尾处重新加入队列重复该操作 k-1 次则在 k−1 次操作之后队首元素即为这一轮中数到的第 k 名小伙伴的编号将队首元素取出即为数到的第 k 名小伙伴离开圈子。上述操作之后新的队首元素即为下一轮游戏的起始小伙伴的编号。每一轮游戏之后圈子中减少一名小伙伴队列中减少一个元素。重复上述过程直到队列中只剩下 1 个元素该元素即为获胜的小伙伴的编号。代码Python3class 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]Javaclass Solution { public int findTheWinner(int n, int k) { QueueInteger queue new ArrayDequeInteger(); 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) { Queueint queue new Queueint(); 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(); } }Cclass Solution { public: int findTheWinner(int n, int k) { queueint 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 个元素。