作为笨蛋的我终于弄懂了圆圈中最后剩下的数字（约瑟夫环问题）暴力求解和数学解法

浅浅的花香味﹌ 2023-07-19 10:50 70阅读 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

也就是经典的约瑟夫环问题，看到题之后我立刻按照题目描述顺着走一遍，最后一次一次循环，肯定是可以找到结果的，这样就是暴力解法：

## 一、暴力解法 ##

直接的思路就是按照题目描述，从5个元素开始，保存，然后初始是0，删除0+3=3第三个（下标2）元素，接着剩4个元素，那么之前的第四个元素（下标3）变成了现在的第三个元素（下标2），然后再删除这四个里面的第3个元素，以此类推，删除位置一直是某位置i+3的话，可以通过模这个数组的长度来获得，第二次要删除的就可以是2-1+3=4，4模4是0，第二次就应该删除第0个元素。

01234；->删除下标为2的
    01 34；->删除下标为0的（2-1+3=4,4%4=0）
     1 34；->删除下标为2的（0-1+3=2,2%3=2）
     1 3 ；->删除下标为0的（2-1+3=4,4%2=0）

##### 因此核心问题，只需要变化的是每次删除之后的下标，这样要创建一个新的数组，然后所有剩下的元素都是按顺序重新排列。所以可以直接使用ArrayList。 #####

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;){
        
                    //注意如果9个元素，第一次就要求删除第13个，那么就是提前要转一圈，所以开始的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 。 #####

##### 现在我们把他们的编号做一下转换：![在这里插入图片描述][20200330172340190.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) 的情况——套娃开始， 这显然就是一个倒推问题！下面举例说明： ####

##### 假设现在是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] #####

#### 现在假设  x’  为 一轮过后的最新情况0,1,2,3,4的解，x  设为原问题的解（这里注意，2,3,4,5,0的解就是0,1,2,3,4,5的解，因为1出去了，结果还是一个），根据观察发现， ####

####  x  与 x’ 关系为 x =(x’+m)%6 ，这里6是n。因此只要求出 x’ ，就可以求 x 。 ####

####  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了。即求  n-1 个人的问题就是找出 n-2  的人的解， ####

#### 那就是说，求 n-2 就是要找出 n-3 ，等等 ####

#### 因此，就可以回去看上面的推导过程了。 ####

#### 我们来写出递推公式 ####

### 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\]，程序也很简单。这个算法的时间复杂度为O(n)，相对于模拟算法已经有了很大的提高。算n，m等于一百万，一千万的情况不是问题了。可见，适当地运用数学策略，不仅可以让编程变得简单，而且往往会成倍地提高算法执行效率。 ####

下面是java代码：

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

其中输入n为个数（人数），m为每次挑选第几个人出局

[20200330172340190.png]: /images/20230528/680f7fe86184449695e9324bf326b24e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5Mjc4Nw_size_16_color_FFFFFF_t_70]: /images/20230528/219d8d8bc7d44efbb9e5d09cacdda99e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5Mjc4Nw_size_16_color_FFFFFF_t_70 1]: /images/20230528/794ab3be04b84c66a37555a7e44f4330.png