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

接上文我们来讲讲第二种解决方案方法二数学 递归思路和算法以下用 f(n,k) 表示 n 名小伙伴做游戏每一轮离开圈子的小伙伴的计数为 k 时的获胜者编号。当 n1 时圈子中只有一名小伙伴该小伙伴即为获胜者因此 f(1,k)1。当 n1 时将有一名小伙伴离开圈子圈子中剩下 n−1 名小伙伴。圈子中的第 k 名小伙伴离开圈子k 满足 1 ≤ k≤ n 且 k - k 是 n 的倍数。由于 1≤k′≤n因此 0≤k′−1≤n−1。又由于 k−k′ 是 n 的倍数等价于 (k-1)-(k-1)是 n 的倍数因此 k′−1(k−1)modnk′(k−1)modn1。当圈子中剩下 n−1 名小伙伴时可以递归地计算 f(n−1,k)得到剩下的 n−1 名小伙伴中的获胜者。令 xf(n−1,k)。由于在第 k 名小伙伴离开圈子之后圈子中剩下的 n−1 名小伙伴从第 k1名小伙伴开始计数获胜者编号是从第 k1名小伙伴开始的第 x 名小伙伴因此当圈子中有 n 名小伙伴时获胜者编号是 f(n,k)(k′modnx−1)modn1(kx−1)modn1。将 xf(n−1,k) 代入上述关系可得f(n,k)(kf(n−1,k)−1)modn1。代码Python3class Solution: def findTheWinner(self, n: int, k: int) - int: return 1 if n 1 else (k self.findTheWinner(n - 1, k) - 1) % n 1Javaclass Solution { public int findTheWinner(int n, int k) { if (n 1) { return 1; } return (k findTheWinner(n - 1, k) - 1) % n 1; } }C#public class Solution { public int FindTheWinner(int n, int k) { if (n 1) { return 1; } return (k FindTheWinner(n - 1, k) - 1) % n 1; } }Cclass Solution { public: int findTheWinner(int n, int k) { if (n 1) { return 1; } return (k findTheWinner(n - 1, k) - 1) % n 1; } };复杂度分析时间复杂度O(n)其中 n 是做游戏的小伙伴数量。需要计算的值有 n 个每个值的计算时间都是 O(1)。空间复杂度O(n)其中 n 是做游戏的小伙伴数量。空间复杂度主要取决于递归调用栈的深度为 O(n) 层。