1823. 找出游戏的获胜者

大家好，我是 @负雪明烛。👈👈 点击关注，优质题解不间断。

题目大意

个人围成一个圈，每次数 个数，被数到的那个人出局。问，圆圈中剩下的最后的一个人的标号。

这是经典的「约瑟夫环」问题。

本文是我「负雪明烛」于 2020-03-31 创作的《这或许是你能找到的最详细约瑟夫环数学推导！》。

由于文章是之前写的，因此下文中变量和本题目有些不对应，但不影响理解：

• 下文中的 就是题目中的 ；
• 下文中是从 编号的，题目是从 编号的，因此代码里面最后的返回结果需要 .

解题方法

问题描述

约瑟夫环问题是这样的：

这 个数字排成一个圆圈，从数字 0 开始，每次从这个圆圈里删除第 个数字。求出这个圆圈里剩下的最后一个数字。

例如， 这 5 个数字组成一个圆圈，从数字 0 开始每次删除第 3 个数字，则删除的前 4 个数字依次是 ，因此最后剩下的数字是 。如下图所示。

解法

解决约瑟夫环问题，我们采用倒推，我们倒推出：最后剩下的这个数字，在最开始的数组中的位置。

1. 剩下最后一个数字（简称“它”）的时候，总个数为 1，它的位置 。
2. 那么它在上一轮也是安全的，总个数为 2，它的位置 %20%5C%25%202#card=math&code=pos%20%3D%20%280%20%2B%20m%29%20%5C%25%202&id=KvPPt)；
3. 那么它在上上轮也是安全的，总个数为 3，它的位置 %20%5C%25%202%20%2B%20m)%20%5C%25%203#card=math&code=pos%20%3D%20%28%280%20%2B%20m%29%20%5C%25%202%20%2B%20m%29%20%5C%25%203&id=eoVwm)；
4. 那么它在上上上轮也是安全的，总个数为 4，它的位置 %20%5C%25%202%20%2B%20m)%20%5C%25%203)%20%5C%25%204#card=math&code=pos%20%3D%20%28%28%280%20%2B%20m%29%20%5C%25%202%20%2B%20m%29%20%5C%25%203%29%20%5C%25%204&id=yOkXN)；
5. …
6. 那么它在游戏开始的第一轮也是安全的，总个数为 ，它的位置 就是最后的结果。

即如果从下向上反推的时候：假如它前一轮的索引为 ，那么当前轮次的位置就是 %20%5C%25#card=math&code=%28pos%20%2B%20m%29%20%5C%25&id=atyQf) 当前轮次的人数。

最后，由于给出的数字是 ，即 ，因此找出 就相当于找到这个数字。

大部分解法解到这里就结束了，缺乏递推公式的数学证明，现就数学推导说明如下。

数学推导

定义：

1. 约瑟夫环操作：把一些数字排成一个圆圈，从数字 0 开始，每次从这个圆圈里删除第 个数字，直到最后只剩一个数字。
2. 函数 #card=math&code=f%28n%2C%20m%29&id=uaJug) ：表示对 个数字 做约瑟夫环操作，最后剩下的这个数字。（这个定义特别重要，理解之后才向下看）

下面开始推导。

整体思路：

• 在以 0 为起始的长度为 的序列上做约瑟夫环操作的最终结果 %3D#card=math&code=f%28n%2C%20m%29%3D&id=CNXlL)
  在完成上轮操作删除数字 之后的新序列上的约瑟夫环操作的最终结果 %3D#card=math&code=h%28n%20-%201%2C%20m%29%3D&id=cDzT3)
  将新序列映射成以 0 为起始的长度为 的序列上的约瑟夫环操作的最终结果 #card=math&code=f%28n%20-%201%2C%20m%29&id=ClfYn) 的逆映射。
• 得到下次操作的新序列

在 这 个数字中，第一个被删除的数字是 %20%5C%25%20n#card=math&code=%28m%20-%201%29%20%5C%25%20n&id=gij9x)。为了简单起见，我们把 %20%5C%25%20n#card=math&code=%28m%20-%201%29%20%5C%25%20n&id=kG71s) 记为 ，那么删除 之后剩下的 个数字为 ，并且下一次删除时要从 开始计数。相当于在剩下的序列中， 排在最前面，所以第二次操作的序列是 。

1. 得到新序列上函数

在这个新序列上再完成约瑟夫环操作，最后剩下的数字应该是关于 和 的函数，即也可以用 #card=math&code=f%28n%2C%20m%29&id=ZUuPn) 进行表示。但由于现在的这个序列的排列（从 开始）和最初的序列（从 0 开始）不一样，因此这个时候的函数已经不同于最初的函数，记为 #card=math&code=h%28n%20-%201%2C%20m%29&id=LMoeS)，此函数的定义：在 这 个数字的序列上做约瑟夫环操作，最后剩下的这个数字。

1. 求解新函数

由于 在最初序列上 和 在新序列上 完成约瑟夫操作剩下的数字均为同一个数字，所以有 %20%3D%20h(n%20-%201%2C%20m)#card=math&code=f%28n%2C%20m%29%20%3D%20h%28n%20-%201%2C%20m%29&id=QerQu)。（新序列是从最初序列转化的，会最终转化到同一个数字）

下面的工作就是求解新函数 #card=math&code=h%28n%20-%201%2C%20m%29&id=Z9AWO) ，使其能够用 #card=math&code=f%28n%20-%201%2C%20m%29&id=SBZVx) 表示出来。

由于 #card=math&code=f%28n%20-%201%2C%20m%29&id=SQAvI) 是定义在以 0 为开始的序列上的，所以我们把剩下的这 个数字的序列 进行映射，映射到结果是形成一个 的序列。

• 
  
  …
  
  
  
  …
  

该映射函数是个一元一次函数，定义为 #card=math&code=p%28x%29&id=wEgH2)，则 %20%3D%20(x%20%2B%20n%20-%20k%20-%201)%20%5C%25%20n#card=math&code=p%28x%29%20%3D%20%28x%20%2B%20n%20-%20k%20-%201%29%20%5C%25%20n&id=yfaNq)。（还记得初中的 怎么求么？如果不懂见附录1）

从左到右的映射是 #card=math&code=p%28x%29&id=c8A3Q)，从右到左的映射叫做逆映射 %20%3D%20(x%20%2B%20k%20%2B%201)%20%5C%25%20n#card=math&code=p%5E%7B-1%7D%28%20x%29%20%3D%20%28x%20%2B%20k%20%2B%201%29%20%5C%25%20n&id=ak3kd)。（该逆映射的求法见本章结尾附录2）

由于映射之后的序列和最初的序列有同样的形式，即都是从 0 开始的连续序列，因此在映射之后的序列上做约瑟夫环操作的结果仍可以用函数 表示，记为 #card=math&code=f%28n%20-%201%2C%20m%29&id=XrErA)。

在映射之前的序列上的约瑟夫环操作的结果是 #card=math&code=h%28n%20-%201%2C%20m%29&id=hZwlg)，在映射之后的序列上的约瑟夫环操作的结果是 #card=math&code=f%28n%20-%201%2C%20m%29&id=o0spK)，则 %20%3D%20p(%20h(n%20-%201%2C%20m)%20)#card=math&code=f%28n%20-%201%2C%20m%29%20%3D%20p%28%20h%28n%20-%201%2C%20m%29%20%29&id=QTPVm)。

所以有：

%20%3D%20p%5E%7B-1%7D(x)(%20f(n%20-%201%2C%20m)%20)%20%3D%20%5B%20f(n%20-%201%2C%20m)%20%2B%20k%20%2B%201%5D%20%5C%25%20n%0A#card=math&code=h%28n%20-%201%2C%20m%29%20%3D%20p%5E%7B-1%7D%28x%29%28%20f%28n%20-%201%2C%20m%29%20%29%20%3D%20%5B%20f%28n%20-%201%2C%20m%29%20%2B%20k%20%2B%201%5D%20%5C%25%20n%0A&id=H5bKh)

把 %20%5C%25%20n#card=math&code=k%20%3D%20%28m%20-%201%29%20%5C%25%20n&id=V1qVB) 代入得到：（ 中有取余运算，为什么代入之后没有了？见本章结尾附录3）

%20%3D%20h(n%20-%201%2C%20m)%20%3D%20%5B%20f(n%20-%201%2C%20m)%20%2B%20m%20%5D%20%5C%25%20n%0A#card=math&code=f%28n%2C%20m%29%20%3D%20h%28n%20-%201%2C%20m%29%20%3D%20%5B%20f%28n%20-%201%2C%20m%29%20%2B%20m%20%5D%20%5C%25%20n%0A&id=g0KYf)

终于，经过复杂的分析，我们找到了一个只包含有 函数的递推公式。要得到 个数字的序列中完成约瑟夫环操作最后剩下的数字，只需要得到 个数字的序列中最后剩下的数字，并以此类推。（像不像递归？）

当 时，也就是序列中只有 1 个数字 0，那么完成约瑟夫操作最后剩下的数字就是0。（像不像递归终止条件？）

我们把这种关系表示为：

%3D%0A%5Cbegin%7Bcases%7D%0A0%20%26%20n%20%3D%201%5C%5C%0A%5Cleft%5Bf(n%20-%201%2C%20m)%20%2B%20m%5Cright%5D%5C%25%20%20n%20%26%20%20n%3E1%0A%5Cend%7Bcases%7D%0A#card=math&code=f%28x%29%3D%0A%5Cbegin%7Bcases%7D%0A0%20%26%20n%20%3D%201%5C%5C%0A%5Cleft%5Bf%28n%20-%201%2C%20m%29%20%2B%20m%5Cright%5D%5C%25%20%20n%20%26%20%20n%3E1%0A%5Cend%7Bcases%7D%0A&id=W31U8)

这个公式无论是递归还是循环都很好实现。

附录1. #card=math&code=p%28x%29&id=dyXSc)的推导

看到这里的同学肯定好奇公式中的%号是怎么得到的，其实是个分段函数归纳的。

%3D%0A%5Cbegin%7Bcases%7D%0Ax%20-%20k%20-%201%20%26%20k%20%2B%201%20%5Cleq%20x%20%5Cleq%20n%20-%201%5C%5C%0Ax%20%2B%20n%20-%20k%20-%201%20%26%200%20%5Cleq%20x%20%5Cleq%20k%20-%201%0A%5Cend%7Bcases%7D%0A#card=math&code=p%28x%29%3D%0A%5Cbegin%7Bcases%7D%0Ax%20-%20k%20-%201%20%26%20k%20%2B%201%20%5Cleq%20x%20%5Cleq%20n%20-%201%5C%5C%0Ax%20%2B%20n%20-%20k%20-%201%20%26%200%20%5Cleq%20x%20%5Cleq%20k%20-%201%0A%5Cend%7Bcases%7D%0A&id=f1Jip)

所以，为了把分段函数统一，使用 %20%3D%20(x%20%2B%20n%20-%20k%20-%201)%20%5C%25%20n#card=math&code=p%28x%29%20%3D%20%28x%20%2B%20n%20-%20k%20-%201%29%20%5C%25%20n&id=B4bsd)。

附录2. #card=math&code=p%5E%7B-1%7D%28x%29&id=LqxSR)的推导

已知%20%3D%20(x%20%2B%20n%20-%20k%20-%201)%20%5C%25%20n#card=math&code=p%28x%29%20%3D%20%28x%20%2B%20n%20-%20k%20-%201%29%20%5C%25%20n&id=ov2fv)，求 #card=math&code=p%5E%7B-1%7D%28x%29&id=P6MFw)。

%20%3D%20(x%20%2B%20n%20-%20k%20-%201)%20%5C%25%20n%20%3D%20(x%20%2B%20n%20-%20k%20-%201)%20%2B%20(T%20-%201)n%20%3D%20x%20-%20k%20-%201%20%2B%20Tn%0A#card=math&code=p%28x%29%20%3D%20%28x%20%2B%20n%20-%20k%20-%201%29%20%5C%25%20n%20%3D%20%28x%20%2B%20n%20-%20k%20-%201%29%20%2B%20%28T%20-%201%29n%20%3D%20x%20-%20k%20-%201%20%2B%20Tn%0A&id=eDVyA)

其中引入的正整数 T 的取值方法：取合适的 T 以保证%20%3C%3D%20n#card=math&code=0%20%3C%3D%20p%28x%29%20%3C%3D%20n&id=bUaXD)。（这一步不懂的可以用 %20%3D%20n%20-%20k%20-1#card=math&code=p%280%29%20%3D%20n%20-%20k%20-1&id=e1nFy) 代入，此时 ）

可以得到%20%2B%20k%20%2B%201%20-%20Tn#card=math&code=x%20%3D%20p%28x%29%20%2B%20k%20%2B%201%20-%20Tn&id=fFj6p)，逆函数就是把 x 替换成 #card=math&code=p%28x%29&id=Vu9vy)，把 #card=math&code=p%28x%29&id=or2ZV) 替换成 x。

所以逆函数 %20%3D%20x%20%2B%20k%20%2B%201%20-%20Tn%20%3D%20(x%20%2B%20k%20%2B%201)%20%5C%25%20n#card=math&code=p%5E%7B-1%7D%28x%29%20%3D%20x%20%2B%20k%20%2B%201%20-%20Tn%20%3D%20%28x%20%2B%20k%20%2B%201%29%20%5C%25%20n&id=EIdQZ)。

附录3. 消除括号里的模运算

模运算的四则规则：%20%5C%25%20p%20%3D%20(a%20%5C%25%20p%20%2B%20b%20%5C%25%20p)%20%5C%25%20p#card=math&code=%28a%20%2B%20b%29%20%5C%25%20p%20%3D%20%28a%20%5C%25%20p%20%2B%20b%20%5C%25%20p%29%20%5C%25%20p&id=MRjxF)，选自百度百科。

证明 %20%2B%20%20(m%20-%201)%20%5C%25%20n%20%2B%201%5D%20%5C%25%20n%20%3D%20%5B%20f(n%20-%201%2C%20m)%20%2B%20m%20%5D%20%5C%25%20n#card=math&code=%5B%20f%28n%20-%201%2C%20m%29%20%2B%20%20%28m%20-%201%29%20%5C%25%20n%20%2B%201%5D%20%5C%25%20n%20%3D%20%5B%20f%28n%20-%201%2C%20m%29%20%2B%20m%20%5D%20%5C%25%20n&id=FMlcv) .

左边 = %20%2B%20%20(m%20-%201)%20%5C%25%20n%20%2B%201%5D%20%5C%25%20n#card=math&code=%5B%20f%28n%20-%201%2C%20m%29%20%2B%20%20%28m%20-%201%29%20%5C%25%20n%20%2B%201%5D%20%5C%25%20n&id=a13g1)

• = %20%2B%201)%20%5C%25%20n%20%2B%20%20%20(m%20-%201)%20%5C%25%20n%5D%20%5C%25%20n#card=math&code=%5B%20%28f%28n%20-%201%2C%20m%29%20%2B%201%29%20%5C%25%20n%20%2B%20%20%20%28m%20-%201%29%20%5C%25%20n%5D%20%5C%25%20n&id=RsHu1) ，由于%20%3C%20n%20-%202#card=math&code=0%20%3C%20%E6%98%A0%E5%B0%84%E5%90%8E%E7%9A%84%E5%8F%96%E5%80%BC%20f%28n%20-%201%2C%20m%29%20%3C%20n%20-%202&id=sAKZJ)，所以%20%2B%201%3C%20n%20-%201#card=math&code=1%20%3C%20f%28n%20-%201%2C%20m%29%20%2B%201%3C%20n%20-%201&id=AqGFg)，所以可以添加第一个取余运算。
  = %20%2B%201)%20%20%2B%20%20%20(m%20-%201)%20%5D%20%5C%25%20n#card=math&code=%5B%20%28f%28n%20-%201%2C%20m%29%20%2B%201%29%20%20%2B%20%20%20%28m%20-%201%29%20%5D%20%5C%25%20n&id=AxHOd) ，运用四则运算公式
  = %20%20%2B%20%20m%20%5D%20%5C%25%20n#card=math&code=%5B%20f%28n%20-%201%2C%20m%29%20%20%2B%20%20m%20%5D%20%5C%25%20n&id=pe1yg)
  = 右边

得证。

代码

开始，代表了最后结果只剩下了 1 个数字，这个数字处于第 0 个位置。

循环从数组长度有 2 个开始，即从剩下了两个数字开始计算。

循环到数组中剩下 个人结束，即到达了题目要求的那么多数字，此时的 就是最后剩下的那个数字的在 个数字中位置。

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

复杂度

• 时间复杂度：$O(N)$
• 空间复杂度：$O(1)$

参考文献

1. 《剑指Offer》，本数学推导基于《剑指Offer》中的推导进行了更详细的讲解。
2. 力扣（LeetCode）链接：https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof
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/

总结

1. 本文的证明非常、非常详细，实际不难，有些笔试题中可能会考这个代码。

我是 @负雪明烛 ，刷算法题 1000 多道，写了 1000 多篇算法题解，收获阅读量 300 万。
关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。

• 在刷题的时候，如果你不知道该怎么刷题，可以看 LeetCode 应该怎么刷？
• 如果你觉得题目太多，想在短时间内快速提高，可以看 LeetCode 最经典的 100 道题。
• 送你一份刷题的代码模板：【LeetCode】代码模板，刷题必会
• 我写的 1000 道 LeetCode 题解，都在这里了，免费拿走。