介绍
约瑟夫问题：N个人围成一圈，从约定编号为K的人开始报数，第M个将被杀掉，求最后存活的人编号。比如有5个人，从第一个开始报数，每隔2个就要杀死一人，则出局顺序为2->4->1->5->3，如下
单链表实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
|
package com.eh.ftd.dsa.ds.impl;
/**
* 约瑟夫环
*
* @author David Li
* @create 2020/06/16 18:40
*/
public class JosephBySingleLinkedList {
/**
* 指向约瑟夫环报数的开始元素
*/
private Node first;
/**
* 指向约瑟夫环的最后一个元素(last.next=first)
*/
private Node last;
class Node {
private int num;
private Node next;
public Node(int num) {
this.num = num;
}
}
/**
* 初始化约瑟夫环
*
* @param n 总数
* @return
*/
public JosephBySingleLinkedList(int n) {
if (n < 2) {
throw new RuntimeException("输入有误！");
}
// 构建个数为n的单向循环链表
for (int i = 1; i <= n; i++) {
Node node = new Node(i);
if (i == 1) {
first = node;
last = node;
node.next = node;
continue;
}
last.next = node;
node.next = first;
last = node;
}
}
/**
* 执行约瑟夫环
*
* @param m 每隔多少位
* @param k 从第k个开始
*/
public void run(int m, int k) {
// 由于从第k个开始，first和last要移动k-1位
Node temp = last;
for (int i = 0; i < k - 1; i++) {
temp = temp.next;
}
last = temp;
first = temp.next;
while (true) {
// 定位到要删除元素，first指向该元素
for (int i = 0; i < m - 1; i++) {
last = last.next;
first = first.next;
}
// 输出元素序号
System.out.println(first.num);
// 删除元素
first = first.next;
last.next = first;
// 跳出条件
if (first == last) {
System.out.println("幸存者: " + first.num);
break;
}
}
}
/**
* 用来展示数据，仅供测试用
*/
public void display() {
Node temp = first;
while (true) {
System.out.println(temp.num);
if (temp == last) {
return;
}
temp = temp.next;
}
}
public static void main(String[] args) {
JosephBySingleLinkedList list = new JosephBySingleLinkedList(5);
list.run(2, 1);
}
}
|
运行结果
我们来计算下时间复杂度，由于有n个人，要删除n-1个人需要遍历n-1次， 又每删除一个人都要执行m-1次循环，顾时间复杂度为(n-1) * (m-1)，也就是O(nm)。当n和m很大时，时间复杂度会非常大。
利用数学解法
在优化前先来查找其中有没有数学规律，仍以上面这个例子为例(下标设置从0开始，最后+k即可)，n=5,m=2,k=1，每次移除一个人，将下一个人的编号映射为0，后面的一次递增(注意因为是循环，前面的人在经过删除后要放在后面)
我们使用队列list1表示报数后的编号队列，使用队列list2表示映射后的编号队列
- 第一轮，开始前剩余5个人(0,1,2,3,4)
list1:2，3，4，0
list2:0，1，2，3
此时list2和list1的关系为(new+m) % n，其中new代表映射后的新编号
- 第二轮， 开始前剩余4个人(0,1,2,3)
list1:2，3，0
list2:0，1，2
此时list2和list1的关系为(new+m) % (n-1)
- 第三轮，开始前剩余3个人(0,1,2)
list1:2，0
list2:0，1
此时list2和list1的关系为(new+m) % (n-2)
- 第四轮， 开始前剩余2个人(0,1)
list1:0
list2:0
此时list2和list1的关系为(new+m) % (n-3)
我们设第一轮幸存值编号为x1,第二轮x2,依次类推第4轮编号x4。那么有以下方程式
x4 = (0 + m) % (n - 3) = (0 + 2) % 2 = 0
x3 = (x4 + m) % (n - 2) = (0 + 2) % 3= 2
x2 = (x3 + m) % (n - 1) = (2 + 2) % 4 = 0
x1 = (x2 + m) % (n - 0) = (0 + 2) % 5 = 2
因为我们的编号是从k开始，所以最终结果为x1+k， 如果是0则统一样式不需要+k
java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
package com.eh.ftd.dsa.ds.impl;
/**
* todo
*
* @author David Li
* @create 2020/06/16 22:14
*/
public class JosephByMath {
/**
* 计算幸存值，使用数学方法
*
* @param k 从第几个编号开始
* @param m 每个多少个人
* @param n 总人数
* @return
*/
public static int calculateTheSurvivor(int k, int m, int n) {
int x = 0;
for (int i = 2; i <= n; i++) {
x = (x + m) % i;
}
return (x + k) % n;
}
public static void main(String[] args) {
System.out.println("=======通过单向链表求解约瑟夫问题=======");
JosephBySingleLinkedList linkedList = new JosephBySingleLinkedList(200);
linkedList.run(18, 10);
System.out.println("=======通过数学方法求解约瑟夫问题=======");
System.out.println(calculateTheSurvivor(10, 18, 200));
}
}
|
运行结果
优化后的算法时间复杂度为O(n)，效率提升了m倍。
