剑指Offer 圆圈中剩下的数字（孩子们的游戏）（暴力法&数学法），约瑟夫环问题

叁歲伎倆 2023-02-18 08:22 2阅读 0赞

题目：

> 0,1,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。  
>   
> 例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。  
>   
> 示例 1：  
> 输入: n = 5, m = 3  
> 输出: 3  
> 示例 2：  
> 输入: n = 10, m = 17  
> 输出: 2  
>   
> 限制：  
> 1 <= n <= 10^5  
> 1 <= m <= 10^6

### 分析 ###

做这道题之前我不知道什么什么是约瑟夫环问题（大概率是各种课上老师都提到过，但是忘记了 ）

题目描述本身就已经陈述的很清楚，找下标，每次的规则也给的很清楚，直到出局的只剩最后一个人，那就是答案。

下标的对应也已经和数组链表这些保持了一致，报数也是从 0 开始的。

### 一、暴力法 ###

最直接的思路就是按照题目描述模拟过程。以示例 1 为例：

如果用数组表示：

> \[ 0, 1, 2, 3, 4, 5 \]

第一次删除的是下标为 2 的元素；

> \[ 0, 1, x, 3, 4, 5 \]

下一次从 3 位置开始计算，删除的是下标为 5 的元素：

> \[ 0, 1, x, 3, 4, x \]

下一次从位置 0 开始计算，删除的是下标为 2 的元素，出现问题，已经删过了，所以要 ++，之后的每一次，只要遇到删除过的位置，都要先跳过去不算数，这样的话代码就会涉及多重 while 循环。

我们不妨直接换成可变列表 ，**用 ArrayList** 这样他长度改变的时候对应下标已经在底层实现了相应变化，方便我们进行操作。

> \[ 0, 1, 2, 3, 4, 5 \]

第一次删除的是下标为 2 的元素；

> \[ 0, 1, x, 3, 4, 5 \] --> \[ 0, 1, 3, 4, 5 \]

下一次还是从 2 位置开始计算（此时元素已经不是 2 ，2 被删除了），删除的是下标为 5 的元素：

> \[ 0, 1, 3, 4, x \] --> \[ 0, 1, 3, 4 \]

依次类推

代码实现如下：

class Solution {
        
        public int lastRemaining(int n, int m) {
        
            ArrayList<Integer> list=new ArrayList<Integer>();
            //注意，泛型只能使用引用类型Integer，不能使用基础类型int
            for(int i=0;i<n;i++){
        
                list.add(i);
            }
            for(int i=(m-1)%list.size();list.size()>1;){
        
                 //如果 m > n
                 //那么就是提前要转一圈，所以开始的 i 也要先模长度
                list.remove(i);
                i=(i+m-1)%list.size();
            }
            return  list.get(0);
        }
    }

虽然很简洁的模拟，但是运行时间很长。

因为每次删除元素对于 ArrayList 的底层实现来说都是新建了一个数组，然后把剩下的元素一个一个copy进去，所以很多次循环的操作时间就会非常慢。

### 二、数学法（也是动态规划） ###

为了讨论方便，先把问题稍微改变一下，并不影响原意：

问题描述：

> 0,1,……，n-1 这 n 个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第 m 个数字。 看做人的出局情况：  
> n 个人(编号 0~(n-1)) ，从 0 开始报数，报到 (m-1) 的退出，剩下的人继续从 0 开始报数。求胜利者的编号。

第一个人 ( 编号一定是 m%n-1 ) 出列之后，剩下的 n-1 个人组成了一个**新的约瑟夫环**（以编号为 k=m%n 的人开始，也就是第一个人 m%n-1 的后一个）:

k k+1 k+2 … n-2, n-1 并且从 k 开始报 0 。

现在我们把他们的编号做一下转换：

![在这里插入图片描述][20200616203825888.png]

剩下的人数是 n-1 ：  
上面的蓝色文字，是从 k 开始剩下的数据进行排序，可以看到从 0 开始到 k-1 位置的人都**躲到了最后一个人 n-1 的后面**；（为了直接显示环的开始结束，我们避免讨论下标到头取模，而是直接重新排列）

下面的红色文字，我们直接把编号做了转换，也就是全部减去 k ，让他们变成从 0 开始，这样方便再根据下标找到应该出局的第几个人。

假设我们最后要求的人，下标记为 **x’** ，经过一轮之后他没有出局，那么坐标转换变成 **x** 。

现在来考虑  
既然变换后就完完全全成为了 (n-1) 个人报数的子问题，假如我们知道这个子问题的解：

> 例如 x 是最终的胜利者，那么根据上面这个表把这个 x 变回去不刚好就是 n 个人情况的解吗？（这是一句废话，就是说我们解出了剩下 n-1 个人的情况，显然做一个 +k 运算就知道原来这个人的位置）  
>   
> 与此同时，变回去的公式很简单：**x’=(x+k)%n** (模n是为了避免加 k 之后超过 n )

如何知道(n-1)个人报数的问题的解？对，只要知道(n-2)个人的解就行了。(n-2)个人的解呢？当然是先求(n-3)的情况……套娃开始，明显的**动态规划**了，而且 从上向下 的过程下标难计算，而反过来从子问题求原问题答案的时候下标容易计算。

为了写出动态规划的代码，我们直接来模拟一下这个操作过程：

1.  假设现在是 6 个人（编号从0到5）报数，每次数到第二个人就退出，即 m=2，编号为2-1=1。那么第一次编号为1的人退出圈子，从他之后的人开始算起，序列变为2,3,4,5,0，即问题变成了这 5 个人报数的问题，将序号做一下转换：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5Mjc4Nw_size_16_color_FFFFFF_t_70]
2.  假设 **x’** 为 一轮过后的最新情况 0,1,2,3,4 的解，**x** 为原问题的解，根据观察发现，x 与 x’ 关系为 **x =(x’+m)%6**，（也就是表中黑色加粗部分和红色部分的关系）因此只要求出 x’，就可以求 x 。
3.  继续求解 **x’**，0,1,2,3,4,，同样是第二个 1 出列，变为（2,3,4,0），转换下为：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5Mjc4Nw_size_16_color_FFFFFF_t_70 1]  
    **x’ =( x”+m)%5**，这里 % 后面变成 5 了。
4.  即求 n-1 个人的问题就是找出 n-2 的人的解，n-2 就是要找出 n-3 ，等等 。

我们得到**动态规划的状态转移式**：

令 f \[ i \] 表示 i 个人玩游戏报 m 退出最后胜利者的编号，最后的结果是 f \[ n \]

*  f \[ 1 \]=0; (如果只有一个人，不管怎么样都是他出局)
 *  f \[ i \] = ( f \[ i - 1 \] + m ) % i ; ( i >1 )（i个人玩留在最后的人是i-1完留到最后的人按照上面的公式推导，不过这里面%i的i是在递增变化的，可以看上面的例子推导，当下一次从5个人推人的时候，模6，当下一次从4个人推人的时候，模5）

从 1 到 n 顺序算出 f \[ i \] 的数值，最后结果是 f \[ n \]。因为实际生活中编号总是从1开始，我们输出 f \[ n \] + 1 由于是逐级递推，不需要保存每个 f \[ i \] ,直接把 dp 的空间优化为 O(1)。

class Solution {
        
        public int lastRemaining(int n, int m) {
        
            int fnext=0;
            //有n个人的时候留下的人的编号结果未知数
            //1个人的情况是不会进入循环的，直接返回就是 0 ；
            //其他的人数>=3的情况，需要i开始++,依次按递推公式改变fnext的值
            for(int i=2;i<=n;i++){
        
                fnext=(fnext+m)%i;//从2个人开始
            }
            return fnext;
        }
    }

瞬间清晰简单了很多。数学的重要性啊

[20200616203825888.png]: https://img-blog.csdnimg.cn/20200616203825888.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5Mjc4Nw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200616204612388.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5Mjc4Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5Mjc4Nw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200616204758811.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5Mjc4Nw==,size_16,color_FFFFFF,t_70