环形单链表的约瑟夫(Josephus)问题

题目

据说著名犹太历史学家 Josephus 有过以下故事:在罗马人占领乔塔帕特后,39 个犹太人与 Josephus 及他的朋友躲到一个洞中,39 个犹太人决定宁愿死也不要被敌人抓到,于是决定了一种自杀方式,41 个人排成一个圆圈,由第1个人开始报数,报数到 3 的人就自杀,然后再由下一个人重新报 1,报数到 3 的人再自杀,这样依次下去,直到剩下最后一个人时,那个人可以自由选择自己的命运。这就是著名的约瑟夫问题。现在请用单向环形链表描述该结构并呈现整个自杀过程。

输入:一个环形单向链表的头节点 head 和报数的值 m。
返回:最后生存下来的节点

进阶问题:如果链表节点数为 \(N\),想在时间复杂度为 \(O(N)\) 时完成原问题的要求,该怎么实现?

解答

方法一

直接模拟,这个按部就班写代码即可。

代码

1
2
3
4
5
6
7
8
public class Node {
public int value;
public Node next;

public Node(int value) {
this.value = value;
}
}
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
/**
* 直接法模拟约瑟夫环的删除过程
* @param head 环形单向链表的头节点
* @param m 每隔 m 个节点删除一次
* @return 最后的幸存者
*/
public Node josephusKill(Node head, int m) {
if (head == null || head.next == head || m < 1) { // 输入不合理
return head;
}
Node last = head;
// 找出最后一个节点 last
while (last.next != head) {
last = last.next;
}
int count = 0;
while (head != last) {
if (++count == m) { // 如果报数到了 m
last.next = head.next; // 删除节点
count = 0; // count 重又归零
} else {
last = last.next; // last 往后移动一位
}
head = last.next; // 移动 head 指针,使 head 指针始终保持是 last 指针的下一位
}
return head;
}

方法一的时间复杂度为 \(O(N \times m)\)\(N\) 是节点数。

方法二

公式法。通过找规律,直接利用递推公式来求解。注意,这个公式法并不是书上介绍的方法,而是上个学期在上数据结构课程时老师讲述的方法。具体思路如下。

首先,我们给出公式

J(n, m) = J(J(n - 1, m) + m) % n, if n > 1, J(1, m) = 0

下面,我们就来简单证明一下这个算法。

举例,我们用数字表示每一个人:

\[1,2,3,4,5,6,7,8,9,10,11\]

一共 11 个人,他们排成一排,假设报到 3 的人被杀掉。

  • 刚开始时,头一个人编号是1,从他开始报数,第一轮被杀掉的是编号3的人。
  • 编号4的人从1开始重新报数,这时候我们可以认为编号4这个人是队伍的头。第二轮被杀掉的是编号6的人。
  • 编号7的人开始重新报数,这时候我们可以认为编号7这个人是队伍的头。第三轮被杀掉的是编号9的人。
  • ……
  • 第九轮时,编号2的人开始重新报数,这时候我们可以认为编号2这个人是队伍的头。这轮被杀掉的是编号8的人。
  • 下一个人还是编号为2的人,他从1开始报数,不幸的是他在这轮被杀掉了。
  • 最后的胜利者是编号为7的人。

表格演示(表头代表数组的下标):

0 1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10 11
4 5 6 7 8 9 10 11 1 2
7 8 9 10 11 1 2 4 5
10 11 1 2 4 5 7 8
2 4 5 7 8 10 11
7 8 10 11 2 4
11 2 4 7 8
7 8 11 2
2 7 8
2 7
7

我们用上面的数据验证一下公式的正确性,其中,J(n, m) 表示的是幸存者在这一轮的下标位置:

  • \(J(1, 3) = 0\);只有一个人,此人是最后的幸存者,其在数组中的下标为 0
  • \(J(2, 3) = 1 = (J(1, 3) + 3) \% 2\);还剩 2 个人时
  • \(J(3, 3) = 1 = (J(2, 3) + 3) \% 3\);还剩 3 个人时
  • \(J(4, 3) = 0 = (J(3, 3) + 3) \% 4\)
  • \(J(5, 3) = 3 = (J(4, 3) + 3) \% 5\)
  • ...
  • \(J(11, 3) = 6 = (J(10, 3) + 3) \% 11\);最终计算出待求的情况

我们通过实例只是验证了这一种情况是成立的,这能够很好地辅助我们理解,但是,我们还需要这个公式的具体推导,下面,就以问答的方式来推导这个公式。

问题1:假设我们已经知道 11 个人时,幸存者的下标位置为 6,那么下一轮 10 个人时,幸存者下标的位置是多少?

:我们在第 1 轮杀掉第 3 个人时,后面的人都往前面移动了 3 位,幸存者也往前移动了 3 位,所以他的下标由 6 变成了 3。

问题2:假设我们呢已经知道 10 个人时,幸存者的下标位置为 3,那么上一轮 11 个人时,幸存者下标的位置是多少?

:这可以看成是上一个问题的逆过程,所以由 10 变成 11 个人时,所有人都往后移动 3 位,所以 \(J(11, 3) = J(10, 3) + 3\),不过数组可能会越界,我们可以想象成数组的首尾是相接的环,那么越界的元素就要重新回到开头,所以这个式子还要模取当前的人数(注意,这里是当前数组,在这里就是人数为 11 的这个数组):\(J(11,3) = (J(10, 3) + 3) \% 11\)

问题3:推及到一般情况,人数为 n,报到 m 时,把那个人杀掉,那么数组又是怎么移动的?

:由上面的推导,我们应该很容易就能得出,若已知 n - 1 个人时,幸存者的下标位置为 \(J(n - 1, m)\),那么 n 个人的时候,就是往后移动 m 位,同样的,因为可能数组越界,所以式子要变成:\(J(n, m) = (J(n - 1, m) + 3) \% n\)

代码

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
/**
* 使用公式法求解最后幸存的节点
* @param head 单向环状链表头节点
* @param m 报数到 m 就删去一个节点
* @return 最后生存的节点
*/
public Node JosephusKillFormula(Node head, int m) {
int n = 0; // n 表示链表的长度
Node last = head;
while (last.next != head) {
n++;
last = last.next;
}
n++;
int p = 0; // 只剩一个人时,数组下标为 0
// 这个循环就是关键的核心
for (int i = 2; i <= n; i++) {
p = (p + m) % i; // i 是当前的人数
}
p += 1; // 因为 p 是从 0 开始,所以最后要加一
while (--p != 0) {
last = last.next;
head = head.next;
}
last.next = null;
head.next = null; // 只取最后的 head 这一个节点,其他都舍去
return head;
}