圆圈中最后剩下的数字

## 1 题目

0,1,···,n-1 这 n 个数字排成一个圆圈，从数字 0 开始，每次从这个圆圈里删除第 m 个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。

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

**示例 1：**

```txt
输入: n = 5, m = 3
输出: 3
```

**示例 2：**

```txt
输入: n = 10, m = 17
输出: 2
```

**限制：**

* 1 <= n <= 10^5
* 1 <= m <= 10^6

## 2 问题分析

1. 该题目是经典的[约瑟夫问题](https://zh.wikipedia.org/wiki/%E7%BA%A6%E7%91%9F%E5%A4%AB%E6%96%AF%E9%97%AE%E9%A2%98)，即：

1. $N$**个人围成一圈**，**第一个人从 1 开始报数**，**报 $M$ 的将被杀掉**，**下一个接着从 1 开始报**，**如此反复**，**最后剩下一个**，**求最后的胜利者**。
2. **约瑟夫环是一个经典的数学问题**，**我们不难发现这样的依次报数**，**似乎有规律可循**，**为了方便导出递推式**，**我们重新定义一下题目**：

1. **$N$ 个人编号为 $ 1, 2,..., N$**，**依次报数**，**每报到 $M$ 时**，**杀掉那个人**，**求最后胜利者的编号**。
3. 下面我们开始求约瑟夫环的递推公式：

1. **下面我们不用字母表示一个人**，**而用数字**：

$$
      1、2、3、4、5、6、7、8、9、10、11
      $$
   2. **上面的数字表示 11 个人**，**他们先排成一排**，**假设每报到 3 的人被杀掉**：

1. **刚开始时**，**头一个人编号是 1**，**从他开始报数**，**第一轮被杀掉的是编号 3 的人**。
      2. **编号 4 的人从 1 开始报数**，**这时候我们可以认为编号 4 这个人是队伍的头**，**第二轮被杀掉的是编号 6 的人**。
      3. **编号 7 的人开始重新报数**，**这个时候我们可以认为编号 7 这个人是队伍的头**，**第三轮杀掉的是编号 9 的人**。
      4. ......
      5. **第九轮时**，**编号 2 的人开始重新报数**，**这时候我们可以认为编号 2 这个人是队伍的头**，**这轮被杀掉的是编号 8 的人**。
      6. **下一个人还是编号为 2 的人**，**他从 1 开始报数**，**不幸的是他在这轮被杀掉了**。
      7. **最后的胜利者是编号为 7 的人**。
   3. 下图表示这一过程（先忽视绿色的一行）：

![这里写图片描述](/media/202202/2022-02-12_1649310.6907512898666288.png)
   4. 我们定义 $f(n, m)$**表示 $N$ 个人报数**，**每报到 $M$ 时杀掉那个人**，**最终胜利者的编号**，下面我们来推导具体的递推公式：

1. **假设我们已经知道 11 个人时胜利者的下标位置为 6**，**在求下一轮 10 个人时**，**由于第一轮删掉编号为 3 的人后**，**之后的人都往前面移动了 3 位**，**胜利者也往前移动了 3 位**，**所以最终胜利者的下标位置由 6 变成 3**。
      2. **假设我们已经知道 10 个人时胜利者的下标位置为 3**，**求上一轮 11 个人时胜利者的下标位置可以看作是上一问题的逆过程**，**大家都往后移动 3 位**，**所以 $f(11, 3) = f(10, 3) + 3$**，**不过有可能数组会越界**，**所以最后模上当前人数的个数**，**即 $f(11, 3) = f(10, 3) \% 11$**。
      3. **现在人数改为 $N$**，**报到 $M$ 时**，**把那个人杀掉**，**因为每杀掉一个人**，**下一个人成为头**，**相当于把数组向前移动 $M$ 位**，**若已知 $N - 1$ 个人时**，**胜利者的下标位置为 $f(N - 1, M)$**，**则 $N$ 个人的时候**，**就是往后移动 $M$ 位**，**因为有可能数组越界**，**越界的部分会被接到头上**，**所以还要模 $N$**，**即 $f(N, M) = (f(N - 1, M) + M) \% n$**。
   5. 因此最终的递推公式为：

$$
      f(N, M) = (f(N - 1, M) + M) \% n
      $$

## 3 参考代码

```java
/**
 * 剑指 Offer 62. 圆圈中最后剩下的数字
 * @param n 数字的个数
 * @param m 删除数字时的间隔
 * @return  圆圈里剩下的最后一个数字
 */
public int lastRemaining(int n, int m) {
    int dp = 0;
    for (int i = 2; i <= n; i++) {
        dp = (dp + m) % i;
    }
    return dp;
}
```

## 参考文献

1. [剑指 Offer 62. 圆圈中最后剩下的数字](https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof)。
2. [约瑟夫环——公式法（递推公式）](https://blog.csdn.net/u011500062/article/details/72855826)。