据说著名的犹太历史学家Josephus有过以下故事， 罗马人占领乔塔帕特， 39个犹太人与Josephus和他的朋友躲在洞中，其中39个犹太人决定自杀，
，他们的自杀方式是41个人绕成一圈，第一个人报数1，报数到3的人自杀。然后新一个人重新报数为1。最终活下来的人可以自由选择自己的命运。当剩下约瑟夫斯和他朋友时，说服了对方，选择向罗马军队投降，不再自杀。
约瑟夫斯把他的存活归因于运气或天意，他不知道是哪一个。其实，这是一个数学问题。
前置准备
初阶部分：链表组织结构， 模拟上述的过程求解。（本解法在洛谷中只能过部分用例。考察基本的coding）😏
进阶部分:数学和递归，迭代解法。 给定洛谷题中不需要链表组织了， 但建议读者写一份链表版本的结构代码
题目:约瑟夫环
直观解法:模拟
一种直观的解法。
将[1,n]的数据以循环单链表的形式存储。然后模拟计数过程自杀过程。
定义一个count变量， 当count报到k的时候就执行链表的删除， 然后重置count。
- 定义一个Main类， 里面定义一个内部类
Node。
java">static class Node {int val;Node next;public Node(int val) {this.val = val;}}
构建[1,n]的循环单链表
java">public static Node createList(int n) {if(n < 1) {return null;}//构建[1...n]的序列Node head = new Node(1);Node tail = head;for(int i=2;i<=n;i++) {tail.next = new Node(i);tail = tail.next;}tail.next = head;//成环。return head;}
模拟约瑟夫环逻辑， 返回最后存在的节点
java">public static Node josephusKilll(Node head, int k) {//链表为空，单节点的循环链表，输入k不合理的逻辑。if(head==null||head.next==head || k < 1) {return head;}Node last = head;//last是head的前驱节点while(last.next!=head) {last = last.next;}int count = 0;//计数变量while(head != last) {if(++count == k) {last.next = head.next;//删除head引用节点count = 0;//重新计数}else {last = last.next;}head = last.next;}return head;}
compute函数:返回最后存活节点的编号
java">public static int compute(int n, int k) {Node head = createList(n);//创建单向循环链表head = josephusKilll(head, k);//返回约瑟夫环最后的节点。return head==null?-1:head.val;}
main函数处理输入输出逻辑
java">public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));StreamTokenizer in = new StreamTokenizer(br);PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));in.nextToken();int n = (int) in.nval;in.nextToken();int k = (int) in.nval;out.println(compute(n,k));out.close();br.close();}
Main类
java">import java.io.*;public class Main {static class Node {int val;Node next;public Node(int val) {this.val = val;}}public static Node createList(int n) {if(n < 1) {return null;}//构建[1...n]的序列Node head = new Node(1);Node tail = head;for(int i=2;i<=n;i++) {tail.next = new Node(i);tail = tail.next;}tail.next = head;//成环。return head;}public static Node josephusKilll(Node head, int k) {//链表为空，单节点的循环链表，输入k不合理的逻辑。if(head==null||head.next==head || k < 1) {return head;}Node last = head;//last是head的前驱节点while(last.next!=head) {last = last.next;}int count = 0;//计数变量while(head != last) {if(++count == k) {last.next = head.next;//删除head引用节点count = 0;//重新计数}else {last = last.next;}head = last.next;}return head;}public static int compute(int n, int k) {Node head = createList(n);//创建单向循环链表head = josephusKilll(head, k);//返回约瑟夫环最后的节点。return head==null?-1:head.val;}public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));StreamTokenizer in = new StreamTokenizer(br);PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));in.nextToken();int n = (int) in.nval;in.nextToken();int k = (int) in.nval;out.println(compute(n,k));out.close();br.close();}
}提交代码到洛谷上
呃， 超时了。
模拟时间复杂度分析
由于0<n,k<10^6 。
删除一个节点要循环k次，一共要删除n-1个节点。
总的时间复杂度 O ( n k ) O(nk) O(nk), 当k,n都取最大时，k与n是线性关系，时间复杂度可认为 O ( n 2 ) O(n^2) O(n2)。
因此， 对于简单小的数据测试量还可以， 但规模一大逃不开超时的命运。
解决方案2
方案1的方法， 在于不知道最后哪个节点能活下来， 只能靠着计数模拟的方式， 一步一步淘汰节点， 通过存在留下的节点确定最终节点。
那么， 有没有更高效的方式。比如，给我一个通项公式直接求出来， 或者递推公式递推一下求出最后的节点。
假设环形链表是1->2->3->4->5->1, 节点数是5，报数m是3。
那么最终节点是4活下来。
| 节点 | 编号 |
|---|---|
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
| 4 | 4 |
| 5 | 5 |
干掉报数为3的节点， 这里标记为-表示被干掉了。
| 节点 | 编号 |
|---|---|
| 1 | 3 |
| 2 | 4 |
| 3 | - |
| 4 | 1 |
| 5 | 2 |
继续
| 节点 | 编号 |
|---|---|
| 1 | - |
| 2 | 1 |
| 3 | - |
| 4 | 2 |
| 5 | 3 |
重复
| 节点 | 编号 |
|---|---|
| 1 | - |
| 2 | 1 & 3 |
| 3 | - |
| 4 | 2 |
| 5 | - |
最后，节点数小于m了，要重复报数了。
发现节点2报了3，干掉节点2。
最终节点4存活。
且节点4最后编号是1。
| 节点 | 编号 |
|---|---|
| 4 | 1 |
好的， 我们记录一下最终存活节点的编号。
记作函数Num
| 编号函数Num(i), i是当前存活的节点数量 |
|---|
| Num(1) = 1 |
| Num(2) |
| … |
| Num(i-1) |
| Num(i) |
可以得出上述节点4的编号规律
4->1
4->2
4->2
4->1
4->4
🆗，我们用自然智慧归纳出这个公式。
最后存活节点的编号是1， 请记住我是从编号1开始推导的。
| 老编号 | 删除s后的新编号 |
|---|---|
| 1 | i-s+1 |
| 2 | i-s+2 |
| … | … |
| s-2 | i-2 |
| s-1 | i-1 |
| s | - |
| s+1 | 1 |
| s+2 | 2 |
| … | … |
| i | i-s |
- 接下来有些神奇操作。
- 所有小于S的老编号对于的新编号满足
o l d = n e w + s − i old = new + s - i old=new+s−i这个表达式。- 所有大于S的老编号对于新编号满足
o l d = n e w + s old = new + s old=new+s这个表达式。
- 可以统一两个公式吗?
答案是可以的。
对于2的关系式，
只需要 o l d = ( n e w + s − i − 1 ) % i + 1 old = (new + s - i - 1) \%i + 1 old=(new+s−i−1)%i+1 。
对于1的关系式， o l d = （ n e w + s − i ) % i + 1 old = （new + s - i)\%i + 1 old=（new+s−i)%i+1这个表达式也是成立的。因为$0<=（new + s - i - 1)<S<=i。
因为取模x的范围是[0,x]，所以需要整体右移（-1）和上移（+1）进行调整， 不能单纯%i,因为会改变范围造成错误。
编号和报数的关系
s = （ m − 1 ） % i + 1 s = （m-1） \%i +1 s=（m−1）%i+1
| m：报数 | s：编号 |
|---|---|
| 1 | 1 |
| … | … |
| i | i |
| i+1 | 1 |
| … | … |
| 2i | i |
跟上面老编号和新编号的推导一样，通过取模和拼凑出来[1...i]的范围。
n与m的关系
老编号 = （新编号 + s − 1 ) % i + 1 老编号 = （新编号 + s - 1) \%i + 1 老编号=（新编号+s−1)%i+1
s = （ m − 1 ） % i + 1 s = （m-1） \%i +1 s=（m−1）%i+1
推导:
老编号 = ( 新编号 + ( m − 1 ) % i ) % i + 1 老编号 = (新编号 + (m-1)\%i) \%i +1 老编号=(新编号+(m−1)%i)%i+1
化简:
老编号 = ( 新编号 + m − 1 ) % i + 1 老编号 = (新编号 + m-1) \%i +1 老编号=(新编号+m−1)%i+1
设 f ( n , k ) , n 为当前节点总数， k 为报数 f(n,k), n为当前节点总数，k为报数 f(n,k),n为当前节点总数，k为报数。
有 f ( n , k ) = ( f ( n − 1 , k ) + m − 1 ) % i + 1 f(n,k) = (f(n-1,k) + m - 1)\%i + 1 f(n,k)=(f(n−1,k)+m−1)%i+1。
代码
迭代法重写compute函数即可， 不需要改上面的main函数
java">public static int compute(int n, int k){int ans = 1;//初始编号为1for(int i=2;i<=n;i++) {ans = (ans + k-1)%i + 1;//自下而上递推公式往上推。}return ans;}
perfect
递归法
本题递归过不了， 栈溢出报RE了。
java">public static int compute(int n, int k) {if(n==1) {return 1;//编号从1开始}else {return (compute(n-1,k)+k-1)%n+1;}}
参考和小小吐槽
本题唯一凹点是数学。
程序员代码面试指南这本书给了图解分析出解析式的推导
严格的数学推导
最后， 本题是线性递推，递归子问题严格不会重叠。 不知道为什么有些题标着动态规划的标签。🧐
最后
链表版本的josephusKilll， 感谢您的阅读。
java">public static Node josephusKilll(Node head, int k) {// 如果链表为空，或者链表中只有一个节点，或者k不合理（k < 1），直接返回原始链表if (head == null || head.next == head || k < 1) {return head;}// 初始化指针，指向链表的第二个节点，并开始计算链表中节点的数量Node cur = head.next;int n = 1; // 初始化节点数为1（因为head节点也算在内）// 遍历链表，计算链表的总长度nwhile (cur != head) { n++; // 每次循环增加1，表示链表的节点数量cur = cur.next; // 指针移动到下一个节点}// 使用compute(n, k)函数，计算约瑟夫环中最后幸存者的编号// 该编号是从1开始计算的n = compute(n, k);// 根据计算出的编号，移动到链表中对应的节点位置// n表示最终幸存者的位置，需要遍历链表n-1次while (--n != 0) {head = head.next; // 移动到下一个节点}// 最终head指向的是约瑟夫环中最后剩下的节点，将该节点的next指向自己// 这样就将链表中其他节点删除，形成单节点循环链表head.next = head;// 返回幸存的节点return head;
}
