【算法】约瑟夫环问题
据说著名的犹太历史学家Josephus有过以下故事， 罗马人占领乔塔帕特， 39个犹太人与Josephus和他的朋友躲在洞中，其中39个犹太人决定自杀，
，他们的自杀方式是41个人绕成一圈，第一个人报数1，报数到3的人自杀。然后新一个人重新报数为1。最终活下来的人可以自由选择自己的命运。当剩下约瑟夫斯和他朋友时，说服了对方，选择向罗马军队投降，不再自杀。
约瑟夫斯把他的存活归因于运气或天意，他不知道是哪一个。其实，这是一个数学问题。
前置准备
- 数据结构-链表
- 本题至少需要了解链表删除节点的逻辑，和循环链表的概念
初阶部分：链表组织结构， 模拟上述的过程求解。（本解法在洛谷中只能过部分用例。考察基本的coding）😏
进阶部分:数学和递归，迭代解法。 给定洛谷题中不需要链表组织了， 但建议读者写一份链表版本的结构代码
题目:约瑟夫环
直观解法:模拟
一种直观的解法。
将[1,n]的数据以循环单链表的形式存储。然后模拟计数过程自杀过程。
定义一个count变量， 当count报到k的时候就执行链表的删除， 然后重置count。
- 定义一个Main类， 里面定义一个内部类
Node。
static class Node {
int val;
Node next;
public Node(int val) {
this.val = val;
}
}
构建[1,n]的循环单链表
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;
}
compute函数:返回最后存活节点的编号
public static int compute(int n, int k) {
Node head = createList(n);//创建单向循环链表
head = josephusKilll(head, k);//返回约瑟夫环最后的节点。
return head==null?-1:head.val;
}
main函数处理输入输出逻辑
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类
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函数
public static int compute(int n, int k){
int ans = 1;//初始编号为1
for(int i=2;i<=n;i++) {
ans = (ans + k-1)%i + 1;//自下而上递推公式往上推。
}
return ans;
}
perfect
递归法
本题递归过不了， 栈溢出报RE了。
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， 感谢您的阅读。
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节点也算在内）
// 遍历链表，计算链表的总长度n
while (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;
}