你好，我很帅。
关于约瑟夫环问题，我想你听说过大多数学校的教科书都会落入这个算法问题，除非你刚从大学一年级毕业。 以防万一你没听说过，我还是做个问题的说明
问题说明：编号1-N的n名士兵聚集成一个圆圈，从编号1的士兵开始依次报数(1、2、3…这样依次报数)，数到m的士兵被杀并列，之后的士兵再从1开始报数。 最后剩下一个士兵，要求这个士兵的号码。
有一次，就像蚂蚁面试，面试官让我觉得对原来味道的约瑟夫很好，好家伙，我不会让你独当一面。
但是，作为有几十次面试经验的xxx，我决定假装用最差劲的方法得到。 等面试官问我还有没有其他方法时，我用的是一步一步比一步强的方法。
因此，第一种方法是数组
1、方法1 :序列是真的。 大学一年级第一次遇到这个问题的时候，我是用数组做的，所以我想大部分人都知道怎么做。 方法如下。
1、2、3…n这n个号码用一个数组存储。 如图所示，这里设为n=6、m=3。
然后，不断遍历数组，对于选择的编号，如果选择了编号arr[2]=3，则可以标记为arr[2]=-1，以指示arr[2]中存储的编号已退出
然后，以这种方式遍历数组，并继续标记数组中只有一个元素不是-1。 那样的话，剩下的要素就会成为我们要找的要素。 来演示一下：
这个方法简单吗？ 想法很简单，但编码并不是那么简单。 临界条件特别多，每次遍历数组的最后一个元素时，都必须将下标重置为0。 此外，在遍历时，还必须确定该元素是否为-1。
但是，这个方法并不是一无是处，不管怎么说，它表明我们的思维很严谨。 毕竟临界条件这么多，我可以做对的。
感兴趣的人请动手试着写代码。 请用这个排列方式试试。 千万不要认为很简单。 编码这个过程还是考验人的。
该方法的时间复杂度为o(n*m )，空间复杂度为o(n*m ) )；
面试官：还有其他方法吗？
当然，面试如果不问的话，也必须告诉面试官。 我突然想到了更好的方法呢，
第二种方法，只能取出我第一学期学到的链表。 我用链表告诉大家吧。
2、方法2 :通过链接列表学习链接列表的人，一般认为会通过链接列表处理约瑟夫林链接问题。 用链表处理，其实和上述处理的想法相同。 但是，在链接列表中处理时，所选号码为3358www.Sina.com/，而不是做标记。 因为要从链接列表中删除元素，当然上面的数组方法也可以采用删除方法，但删除数组所需的时间复杂性是o(n )。 采用链表的解决方法如下
1、首先建立环链表，保存元素。 (直接移除链接列表哦) ) )。
2、然后，多次查询并删除链表，在链表中只剩下一个节点之前，我不会做全部的演示
代码是用Java写的。
代码如下。
//链表节点class Node{ int date； 节点下一步； 公共节点(int date ) { this.date=date； }核心代码
publicstaticintsolve(intn，int m ) if ) m==1|||n2 )返回n； //环形链接列表nodehead=createlinkedlist(n )； //导线测量删除int count=1； 节点Cur=head； 节点pre=null； //前驱节点While(Head.Next！=head(//删除节点if (count==m ) ) { count=1； pre.next=cur.next； cur=pre.next； } else { count； pre=cur； cur=cur.next； } } return head.date； }静态节点描述符(intn )节点头=新节点) 1； 节点下一步=head； for(intI=2； i=n； I )
{ Node tmp = new Node(i); next.next = tmp; next = next.next; } // 头尾串联 next.next = head; return head; }
这种方法估计是最多人用的，时间复杂度为 O(n * m), 空间复杂度是 O(n)。
和第一种方便相比，时间复杂度和空间复杂度都差不多，不过采用链表比较不容易出错。
面试官：还有更好的方法吗？
我：卧槽，链表这么好的方法还问我有没有更好的？好家伙，嫌弃代码太长没耐心看？
方法三：递归
帅地被迫只能拿出我的递归大法，递归是思路是每次我们删除了某一个士兵之后，我们就对这些士兵重新编号，然后我们的难点就是找出删除前和删除后士兵编号的映射关系。
如果你对递归不大懂，可以看我之前的递归文章：连刷半年题，告别递归，谈谈我的一些经验
我们定义递归函数 f(n，m) 的返回结果是存活士兵的编号，显然当 n = 1 时，f(n, m) = 1。假如我们能够找出 f(n，m) 和 f(n-1，m) 之间的关系的话，我们就可以用递归的方式来解决了。我们假设人员数为 n, 报数到 m 的人就自杀。则刚开始的编号为
…
1
…
m – 2
m – 1
m
m + 1
m + 2
…
n
…
进行了一次删除之后，删除了编号为 m 的节点。删除之后，就只剩下 n – 1 个节点了，删除前和删除之后的编号转换关系为：
删除前 — 删除后
… — …
m – 2 — n – 2
m – 1 — n – 1
m —- 无(因为编号被删除了)
m + 1 — 1(因为下次就从这里报数了)
m + 2 —- 2
… —- …
新的环中只有 n – 1 个节点。且删除前编号为 m + 1, m + 2, m + 3 的节点成了删除后编号为 1， 2， 3 的节点。
假设 old 为删除之前的节点编号， new 为删除了一个节点之后的编号，则 old 与 new 之间的关系为 old = (new + m – 1) % n + 1。
有人可能看了会一脸懵逼？如果是这样，那么我建议你自己找几个例子模仿推导一下，估计就知道了
注：有些人可能会疑惑为什么不是 old = (new + m ) % n 呢？主要是因为编号是从 1 开始的，而不是从 0 开始的。如果 new + m == n的话，会导致最后的计算结果为 old = 0。所以 old = (new + m – 1) % n + 1.
这样，我们就得出 f(n, m) 与 f(n – 1, m)之间的关系了，而 f(1, m) = 1.所以我们可以采用递归的方式来做。代码如下：
int f(int n, int m){ if(n == 1) return n; return (f(n – 1, m) + m – 1) % n + 1;}
我去，两行代码搞定，而且时间复杂度是 O(n)，当然，空间复杂度还是 O(n)，因为会递归会调用 n 次。
为了装逼，我必须用用一行代码来搞定，如下：
int f(int n, int m){ return n == 1 ? n : (f(n – 1, m) + m – 1) % n + 1;}
卧槽，以后面试官让你手写约瑟夫问题，你就扔这一行代码给它。这里需要注意的是，如果 n 的数值太大，那么就不适合用递归了，注意怕递归太深，爆栈了
无论是面试还是提升自己的内容，算法学习基本少不了，这里给大家推荐一份某 BAT 大佬总结的 Leetcode 刷题笔记，汇聚了上千道 leetcode 题解，并且代码都是 beat 100%：：BAT 大佬分类总结的 Leetcode 刷题模版，助你搞定 90% 的面试
就算你现在不学算法，那么这份笔记也值得你收藏，万一有人问你 Leetcode 某道题解，或者有大神在讨论题解，咱打开这份笔记，不管三七二十一，直接把最优解扔给他，然后退出群聊
链接：BAT 大佬分类总结的 Leetcode 刷题模版，助你搞定 90% 的面试
总结
不过那次笔试时，并没有用递归的方法做，而是用链表的方式做，，，，，那时，不知道原来还能用一行代码搞定的，，，，欢迎各位大佬提供半行代码搞定的方法！
支付宝扫一扫
微信扫一扫
