php约瑟夫环问题技巧_约瑟夫环问题用这三种方法轻松搞定

文章目录 [+]

什么是约瑟夫环问题？

约瑟夫环问题在不同平台被"优化"描述的不一样，例如在牛客剑指offer叫孩子们的游戏，还有叫杀人游戏，点名……最直接的觉得还是力扣上剑指offer62的描述：圆圈中末了剩下的数字。

php约瑟夫环问题技巧_约瑟夫环问题用这三种方法轻松搞定

问题描述：

（图片来自网络侵删）

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

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

当然，这里考虑m，n都是正常的数据范围，个中

1 <= n <= 10^51 <= m <= 10^6

对付这个问题，你可能脑海中有了印象，想着小时候村落里一群孩子坐在一起，从某个开始报数然后数到几出列，下一个重新开始一贯到末了一个。

循环链表仿照

这个问题最实质实在便是循环链表的问题，围成一个圈之后，就没有结尾这便是一个范例的循环链表嘛！
一个一个顺序报数，那不便是链表的遍历列举嘛！
数到对应数字的出列，这不便是循环链表的删除嘛！

并且这里还有非常方便的地方：

循环链表的向下列举不须要考虑头尾问题，直接node=node.next向下循环聊表的删除也不须要考虑头尾问题，直接node.next=node.next.next删除

当然也有一些须要把稳的地方

形成环形链表很大略，只须要将普通链表的末了一个节点的next指向第一个节点即可循环链表中只有一个节点的时候停滞返回，即node.next=node的时候删除，须要找到待删除的前面节点，以是我们删除计数的时候要少即一位，利用前面的那个节点直接删除后面节点即可

这样，思路明确，直接开撸代码：

classSolution{classnode//链表节点{intval;publicnode(intvalue){this.val=value;}nodenext;}publicintlastRemaining(intn,intm){if(m==1)returnn-1;//一次一个直接返回末了一个即可nodehead=newnode(0);nodeteam=head;//创建一个链表for(inti=1;i<n;i++){team.next=newnode(i);team=team.next;}team.next=head;//使形成环intindex=0;//从0开始计数while(head.next!=head){//当剩余节点不止一个的时候//如果index=m-2那就解释下个节点(m-1)该删除了if(index==m-2){head.next=head.next.next;index=0;}else{index++;}head=head.next;}returnhead.val;}}

当然，这种算法太繁芜了，大部分的OJ你提交上去是无法AC的，由于超时太严重了，详细的我们可以下面剖析。

有序凑集仿照

上面利用链表直接仿照游戏过程会造成非常严重非常严重的超时，n个数字，数到第m个出列。
由于m如果非常大远远大于m，那么将进行很多次转圈圈。

以是我们可以利用求余的方法判断等价最低的列举次数，然后将其删除即可，在这里你可以连续利用自建链表去仿照，上面的while循环以及上面只需添加一个记录长度的每次求余算圈数即可：

intlen=n;while(head.next!=head){if(index==(m-2)%len){head.next=head.next.next;index=0;len--;}else{index++;}head=head.next;}

但我们很多时候不会手动去写一个链表仿照，我们会借助ArrayList和LinkedList去仿照，如果利用LinkedList其底层也是链表，利用ArrayList的话其底层数据构造是数组。
不过在利用List其代码方法同等。

List可以直接知道长度，也可删除元素，利用List的难点是一个顺序表怎们仿照成循环链表？

咱们仔细思考：假设当前长度为n，数到第m个(通过上面剖析可以求余让这个有效的m不大于n)删除，在index位置删除。
那么删除后剩下的便是n-1长度，index位置便是表示第一个计数的位置，我们可以通过求余得知走下一个删除须要多少步，那么下个位置怎么确定呢？

你可以分类谈论看看走的次数是否越界，但这里有更奥妙的方法，可以直接求的下一次详细的位置，公式便是为：

index=(index+m-1)%(list.size());

由于index是从1计数，如果是循环的再往前m-1个便是真正的位置，但是这里可以先假设先将这个有序凑集的长度扩大多少倍，然后从index计数开始找到假设不循环的位置index2，末了我们将这个位置index2%(凑集长度)即为真正的长度。

利用这个公式一举几得，既能把上面m过大循环过多的情形办理，又能找到真实的位置，便是将这个环先假设成线性的然后再去找到真的位置，如果不理解的话可以再看看这个图：

这种情形的话大部分的OJ是可以勉强过关的，口试官的层面也大概率差不多的，详细代码为：

classSolution{publicintlastRemaining(intn,intm){if(m==1)returnn-1;List<Integer>list=newArrayList<>();for(inti=0;i<n;i++){list.add(i);}intindex=0;while(list.size()>1){index=(index+m-1)%(list.size());list.remove(index);}returnlist.get(0);}}递归公式办理

我们回顾上面的优化过程，上面用求余可以办理m比n大很多很多的情形(即理论上须要转很多很多圈的情形)。
但是还可能存在n本身就很大的情形，无论是顺序表ArrayList还是链表LinkedList去频繁查询、删除都是很低效的。

以是聪明的人就开始从数据找一些规律或者关系。

先抛出公式：

f(n,m)=(f(n-1,m)+m)%nf(n,m)指n个人，报第m个编号出列终极编号

下面要负责看一下我的剖析过程：

我们举个例子，有0 1 2 3 4 5 6 7 8 9十个数字，假设m为3,末了结果可以先记成f(10,3)，纵然我们不知道它是多少。

当进行第一次时候，找到元素2 删除，此时还剩9个元素，但起始位置已经变成元素3。
等价成3 4 5 6 7 8 9 0 1这9个数字重写开始找。

此时这个序列终极剩下的一个值即为f(10,3)，这个序列的值和f(9,3)不同，但是都是9个数且m即是3，以是其删除位置是相同的，即算法大体流程是同等的，只是各位置上的数字不一样。
以是我们须要做的事情是找找这个序列上和f(9,3)值上有没有什么联系。

探求过程中别忘却两点，首先可通过%符号对数字有效扩充，即我们可以将3 4 5 6 7 8 9 0 1这个序列算作(3,4,5,6,7,8,9,10,11)%10.这里的10即为此时的n数值。

其余数值如果是连续的，那么终极一个结果的话是可以找到联系的(差值为一个定制)。
以是我们可以就找到f(10,3)和f(9,3)值之间结果的关系，可以看下图：

以是f(10,3)的结果就可以转化为f(9,3)的表达,后面也是同理：

f(10,3)=(f(9,3)+3)%10f(9,3)=(f(8,3)+3)%9……f(2,3)=(f(1,3)+3)%2f(1,3)=0