关键词：力扣，LeetCode，题解，清晰讲解，算法，约瑟夫环，Python，Java，C++
题目地址：https://leetcode-cn.com/problems/find-the-winner-of-the-circular-game/
题目描述
共有n 名小伙伴一起做游戏。小伙伴们围成一圈，按 顺时针顺序 从 1 到 n 编号。确切地说，从第 i 名小伙伴顺时针移动一位会到达第 (i+1) 名小伙伴的位置，其中 1 <= i < n ，从第 n 名小伙伴顺时针移动一位会回到第 1 名小伙伴的位置。
游戏遵循如下规则：
1、 从第1名小伙伴所在位置开始；
2、 沿着顺时针方向数k名小伙伴，计数时需要包含起始时的那位小伙伴逐个绕圈进行计数，一些小伙伴可能会被数过不止一次；
3、 你数到的最后一名小伙伴需要离开圈子，并视作输掉游戏；
4、 如果圈子中仍然有不止一名小伙伴，从刚刚输掉的小伙伴的顺时针下一位小伙伴开始，回到步骤2继续执行；
5、 否则，圈子中最后一名小伙伴赢得游戏给你参与游戏的小伙伴总数n，和一个整数k，返回游戏的获胜者；
示例1： 
输入：n = 5, k = 2
输出：3
解释：游戏运行步骤如下：
1) 从小伙伴 1 开始。
2) 顺时针数 2 名小伙伴，也就是小伙伴 1 和 2 。
3) 小伙伴 2 离开圈子。下一次从小伙伴 3 开始。
4) 顺时针数 2 名小伙伴，也就是小伙伴 3 和 4 。
5) 小伙伴 4 离开圈子。下一次从小伙伴 5 开始。
6) 顺时针数 2 名小伙伴，也就是小伙伴 5 和 1 。
7) 小伙伴 1 离开圈子。下一次从小伙伴 3 开始。
8) 顺时针数 2 名小伙伴，也就是小伙伴 3 和 5 。
9) 小伙伴 5 离开圈子。只剩下小伙伴 3 。所以小伙伴 3 是游戏的获胜者。
示例2：
输入：n = 6, k = 5
输出：1
解释：小伙伴离开圈子的顺序：5、4、6、2、3 。小伙伴 1 是游戏的获胜者。
提示：
- 1
<= k<= n `<= 500
题目大意
n个人围成一个圈，每次数 k 个数，被数到的那个人出局。问：圆圈中剩下的最后的一个人的标号。
这是经典的「约瑟夫环」问题。
本文是我 @负雪明烛open in new window 于 2020-03-31 创作的《这或许是你能找到的最详细约瑟夫环数学推导！》open in new window。
由于文章是之前写的，因此下文中变量和本题目有不对应，但不影响理解：
- 下文中的 m 就是题目中的 k；
- 下文中是从 0 编号的，题目是从 1 编号的，因此代码里面最后的返回结果需要 +1.
解题方法
问题描述
约瑟夫环问题是这样的：
0,1,…,n−1 这 n 个数字排成一个圆圈，从数字 0 开始，每次从这个圆圈里删除第 m 个数字。求出这个圆圈里剩下的最后一个数字。
例如，0、1、2、3、4 这 5 个数字组成一个圆圈，从数字 0 开始每次删除第 3 个数字，则删除的前 4 个数字依次是 2、0、4、1，因此最后剩下的数字是 3。
如下图所示。
根据上图中的箭头，我们可以看到每一轮中移走的是第 m 个数字（因为数组下标是从 0 开始，所以被移走的数字下标为 m−1）。 所以每一轮的第 m+1 个数字（下标为 m），将成为下一轮的开头元素（下标变成 0)。
解法
解决约瑟夫环问题，我们采用倒推，我们倒推出：最后剩下的这个数字，在最开始的数组中的位置。
1、 剩下最后一个数字（简称“它”）的时候，总个数为1，它的下标pos=0；
2、 那么它在上一轮也是安全的，总个数为2，它的下标pos=(0+m)%2；（解释：在上一轮中，它前面的数字（即红色的数字，下标为m−1）被移走了；因此它的下标是m；由于是环，因此需要%2）；
3、 那么它在上上轮也是安全的，总个数为3，它的下标pos=((0+m)%2+m)%3；
4、 那么它在上上上轮也是安全的，总个数为4，它的下标pos=(((0+m)%2+m)%3+m)%4；
5、 ...；
6、 那么它在游戏开始的第一轮也是安全的，总个数为n，它的下标pos就是所求；
即如果从下向上反推的时候：假如它下一轮的下标为 pos，那么当前轮次的下标就是： (pos+m)% 当前轮次的人数。
最后，由于给出的数字是 nums=0,1,2,..,n−1，即 nums[i]=i，因此找出下标 pos 就相当于找到这个数字。
大部分解法解到这里就结束了，缺乏递推公式的数学证明，现就数学推导说明如下。
数学推导
定义：
1、 约瑟夫环操作：把一些数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字，直到最后只剩一个数字；
2、 函数f(n,m)：表示对n个数字0,1,…,n−1做约瑟夫环操作，最后剩下的这个数字（这个定义特别重要，理解之后才向下看）；
下面开始推导。
整体思路：
整体思路如下。看不懂没问题，后文有详细说明：
1、 在以0为起始的、长度为n的序列上做约瑟夫环操作的最终结果f(n,m)=；
2、 在完成上轮操作删除数字k之后的新序列上的约瑟夫环操作的最终结果h(n−1,m)=；
3、 将新序列映射成以0为起始的长度为n−1的序列上的约瑟夫环操作的最终结果f(n−1,m)的逆映射；
注意，每次操作后得到的新序列，数字的排列是有变化的：
- 在 0,1,…,n−1 这 n 个数字中，第一个被删除的数字是 (m−1)%n。为了简单起见，我们把 (m−1)%n 记为 k。
- 那么删除 k 之后剩下的 n−1 个数字为 0,1,…,k−1,k+1,…,n−1，并且下一次删除时要从 k+1 开始计数。
- 相当于在剩下的序列中， k+1 排在最前面，所以第二次操作的序列是 k+1,…,n−1,0,1,…,k−1。
1. 定义新序列上函数
我们希望在这个新序列上再完成约瑟夫环操作，最后剩下的数字应该是关于 n 和 m 的函数，即也可以用 f(n,m) 进行表示。
但由于现在的这个序列的排列（从 k+1 开始）和最初的序列（从 0 开始）不一样。
因此这个时候的函数已经不同于最初的函数，我们记为 h(n−1,m)，此函数的定义：在 k+1,…,n−1,0,1,…,k−1 这 n−1个数字的序列上做约瑟夫环操作，最后剩下的这个数字。
2. 求解新函数
由于 在最初序列上 和 在新序列上 完成约瑟夫操作剩下的数字均为同一个数字，所以有
f(n,m)=h(n−1,m)
下面的工作就是求解新函数 h(n−1,m) ，使其能够用 f(n−1,m) 表示出来。
由于f(n−1,m) 是定义在以 0 为开始的序列上的，所以我们把剩下的这 n−1 个数字的序列 k+1,…,n−1,0,1,…,k−1 进行映射，映射到结果是形成一个 0,..,n−2 的序列。
- k+1→0k+2→1...n−1→n−k−20→n−k−11→n−k...k−1→n−2
接下来的内容很重要：
- 该映射函数是个一元一次函数，定义为 p(x)，可以求出 p(x)=(x+n−k−1)%n。（还记得初中的 y=x+a 怎么求么？如果不会，去看 附录 1）
- 从左到右的映射是 p(x)，从右到左的映射叫做逆映射 p−1(x)=(x+k+1)%n。（该逆映射的求法见本章结尾 附录 2）
- 由于映射之后的序列和最初的序列有同样的形式，即都是从 0 开始的连续序列，因此在映射之后的序列上做约瑟夫环操作的结果仍可以用函数 f 表示，即为 f(n−1,m)。
在映射之前的序列上的约瑟夫环操作的结果是 h(n−1,m)，在映射之后的序列上的约瑟夫环操作的结果是 f(n−1,m)，所以：
f(n−1,m)=p(h(n−1,m))
所以有：
h(n−1,m)=p−1(x)(f(n−1,m))=[f(n−1,m)+k+1]%n
把k=(m−1)%n 代入得到：（k 中有取余运算，为什么代入之后没有了？见本章结尾 附录 3）
f(n,m)=h(n−1,m)=[f(n−1,m)+m]%n
终于，经过复杂的分析，我们找到了一个只包含有 f 函数的递推公式。
- 要得到 n 个数字的序列中完成约瑟夫环操作最后剩下的数字的下标，只需要得到 n−1 个数字的序列中最后剩下的数字的下标。并以此类推。（像不像递归？）
- 当 n=1 时，也就是序列中只有 1 个数字（下标为 0），那么完成约瑟夫操作最后剩下的数字的下标就是 0。（像不像递归终止条件？）
我们把这种关系表示为：
f(x)={0[f(n−1,m)+m]%nn=1n>1
这个公式无论是递归还是循环都很好实现。
至此，主要的数学推导过程已经结束。下面是附录。
附录 1. p(x) 的推导
公式p(x)=(x+n−k−1)%n 中的 % 号是怎么得到的？
其实是个分段函数归纳的。
p(x)={x−k−1x+n−k−1k+1≤x≤n−10≤x≤k−1
所以，为了把分段函数统一，使用 p(x)=(x+n−k−1)%n。
附录 2. p−1(x) 的推导
已知p(x)=(x+n−k−1)%n，求 p−1(x)。
p(x)=(x+n−k−1)%n=(x+n−k−1)+(T−1)n=x−k−1+Tn
其中引入的正整数 T 的取值方法：取合适的 T 以保证 0<=p(x)<=n。（这一步不懂的可以用 p(0)=n−k−1 代入，此时 x=0,T=1）
可以得到x=p(x)+k+1−Tn，逆函数就是把 x 替换成 p(x)，把 p(x) 替换成 x。
所以逆函数 p−1(x)=x+k+1−Tn=(x+k+1)%n。
附录 3. 消除括号里的模运算
模运算的四则规则：(a+b)%p=(a%p+b%p)%p，选自百度百科open in new window。
我们需要证明：
[f(n−1,m)+(m−1)%n+1]%n=[f(n−1,m)+m]%n
证明方法：
- 左边 =[f(n−1,m)+(m−1)%n+1]%n=[(f(n−1,m)+1)%n+(m−1)%n]%n（解释：由于0<映射后的取值f(n−1,m)<n−2，所以1<f(n−1,m)+1<n−1，所以可以添加第一个取余运算。） =[(f(n−1,m)+1)+(m−1)]%n ，运用四则运算公式 =[f(n−1,m)+m]%n= 右边
得证。
代码
代码思路：
- pos=0 开始，代表了最后结果只剩下了 1 个数字，这个数字处于下标为 0 的位置。
- 循环从数组有两个 2 元素开始。
- 当数组中剩下 n 个人结束，即到达了题目要求的那么多数字，此时的 pos 就是最后剩下的那个数字的在 n 个数字的下标。
由于，我上文的分析中，是从 0 开始编号的，题目是从 1 开始编号的，因此返回值是 pos+1。
Python 语言的代码如下：
class Solution(object):
def findTheWinner(self, n, k):
pos = 0
for i in range(2, n + 1):
pos = (pos + k) % i
return pos + 1
1 2 3 4 5 6
C++语言的代码如下：
class Solution {
public:
int findTheWinner(int n, int k) {
int pos = 0;
for (int i = 2; i < n + 1; ++i) {
pos = (pos + k) % i;
}
return pos + 1;
}
};
1 2 3 4 5 6 7 8 9 10
Java 语言的代码如下：
class Solution {
public int findTheWinner(int n, int k) {
int pos = 0;
for (int i = 2; i < n + 1; ++i) {
pos = (pos + k) % i;
}
return pos + 1;
}
}
1 2 3 4 5 6 7 8 9
复杂度
- 时间复杂度：O(N)
- 空间复杂度：O(1)
参考文献
1、 《剑指Offer》，本数学推导基于《剑指Offer》中的推导进行了更详细的讲解；
2、 力扣（LeetCode）链接：[https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcofopeninnewwindow][https_leetcode-cn.com_problems_yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcofopeninnewwindow]；
3、 [https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/javajie-jue-yue-se-fu-huan-wen-ti-gao-su-ni-wei-sh/openinnewwindow][https_leetcode-cn.com_problems_yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof_solution_javajie-jue-yue-se-fu-huan-wen-ti-gao-su-ni-wei-sh_openinnewwindow]；
总结
1、 本文的证明非常非常详细，核心问题在于映射；
2、 有些笔试题中可能会考这个代码；
3、 记得给本题解点个赞👍🏻哦！；
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发