1823. Find the Winner of the Circular Game 找出游戏的获胜者

作者：负雪明烛 id： fuxuemingzhu 个人博客： https://fuxuemingzhu.cn/ 关键词：力扣，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 名小伙伴所在位置开始。
沿着顺时针方向数 k 名小伙伴，计数时需要包含起始时的那位小伙伴。逐个绕圈进行计数，一些小伙伴可能会被数过不止一次。
你数到的最后一名小伙伴需要离开圈子，并视作输掉游戏。
如果圈子中仍然有不止一名小伙伴，从刚刚输掉的小伙伴的顺时针下一位小伙伴开始，回到步骤 2 继续执行。
否则，圈子中最后一名小伙伴赢得游戏。给你参与游戏的小伙伴总数 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$ 个数，被数到的那个人出局。问：圆圈中剩下的最后的一个人的标号。

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

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

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

下文中的 $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$。

如下图所示。

1823. 找出游戏的获胜者.001

根据上图中的箭头，我们可以看到每一轮中移走的是第 $m$ 个数字（因为数组下标是从 $0$ 开始，所以被移走的数字下标为 $m - 1$）。所以每一轮的第 $m + 1$ 个数字（下标为 $m$），将成为下一轮的开头元素（下标变成 $0$)。

解法

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

剩下最后一个数字（简称“它”）的时候，总个数为 $1$，它的下标 $pos = 0$。
那么它在上一轮也是安全的，总个数为 $2$，它的下标 $pos = (0 + m) % 2$； （解释：在上一轮中，它前面的数字（即红色的数字，下标为 $m - 1$）被移走了；因此它的下标是 $m$；由于是环，因此需要 $% 2$）
那么它在上上轮也是安全的，总个数为 $3$，它的下标 $pos = ((0 + m) % 2 + m) % 3$；
那么它在上上上轮也是安全的，总个数为 $4$，它的下标 $pos = (((0 + m) % 2 + m) % 3 + m) % 4$；
…
那么它在游戏开始的第一轮也是安全的，总个数为 $n$，它的下标 $pos$ 就是所求。

即如果从下向上反推的时候：假如它下一轮的下标为 $pos$，那么当前轮次的下标就是： $(pos + m) %$ 当前轮次的人数。

最后，由于给出的数字是 $nums = 0, 1, 2, .., n - 1$，即 $nums[i] = i$，因此找出下标 $pos$ 就相当于找到这个数字。

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

数学推导

定义：

约瑟夫环操作：把一些数字排成一个圆圈，从数字 $0$ 开始，每次从这个圆圈里删除第 $m$ 个数字，直到最后只剩一个数字。
函数 $f(n, m)$ ：表示对 $n$ 个数字 $0, 1, …, n - 1$ 做约瑟夫环操作，最后剩下的这个数字。（这个定义特别重要，理解之后才向下看）

下面开始推导。

整体思路：

整体思路如下。看不懂没问题，后文有详细说明：

在以 $0$ 为起始的、长度为 $n$ 的序列上做约瑟夫环操作的最终结果 $f(n, m)=$
在完成上轮操作删除数字 $k$ 之后的新序列上的约瑟夫环操作的最终结果 $h(n - 1, m)=$
将新序列映射成以 $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 → 0$ $k + 2→ 1$ $…$ $n - 1 → n - k -2$ $0 → n - k - 1$ $1 → 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)= \begin{cases} 0 & n = 1\ \left[f(n - 1, m) + m\right]% n & n>1 \end{cases}$$

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

至此，主要的数学推导过程已经结束。下面是附录。

附录 1. $p(x)$ 的推导

公式 $p(x) = (x + n - k - 1) % n$ 中的 $%$ 号是怎么得到的？

其实是个分段函数归纳的。

$p(x)= \begin{cases} x - k - 1 & k + 1 \leq x \leq n - 1\ x + n - k - 1 & 0 \leq x \leq k - 1 \end{cases}$

所以，为了把分段函数统一，使用 $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$，选自百度百科。

我们需要证明：

$$[ 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

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;
    }
};

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;
    }
}

复杂度

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

参考文献

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