前言
本文编程语言使用Java
问题概述
据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。机智的约瑟夫算出活到最后的位置，逃过一劫。
现在请用环形单链表描述此问题
输入：环形单链表的头节点和报数的值m
返回：最后存活的节点
初步分析
下面我们通过一组数据来模拟这个过程，假设环长n为5，m为3
从上图中我们可以看到模拟过程，当有5个人时，每轮报3的人自杀，最后第4个人活了下来。
普通解法
普通解法非常简单，我们只需遍历环形链表并且记录当前count，删除count = m的节点。
需要注意的是删除链表中的节点只需找到该节点上一个节点即可，下面贴代码
public Node josephusProblem(Node head, int m) {
if (head == null || head.next == null || m < 1) {
return head;
}
int count = 0;//计数变量
while (head.next != null) {//遍历环形链表至只剩下一个节点
if (++count + 1 == m) {//找到需要删除节点的前一节点
if (head == head.next) {//只剩一个节点时
head.next = null;
return head;
}
head.next = head.next.next;//删除节点
count = 0;//计数变量重置
}
head = head.next;
}
return head;
}
因为每删除1个节点都要遍历m次，删除n个节点需要遍历n * m次，时间复杂度为O(n*m)。
O(N)解
上面的解法比较笨重，需要不断的遍历，直到剩下最后一个节点，算法的时间复杂度为O(nm)，问题就在于我们事先不知道最后活下来的节点。那么有没有O(N)的解法呢？现在我们换一种思路，如果我们能直接计算出需要删除的节点的位置*，那么遍历该链表，直接删除就可以了。
我们可以尝试推导出不同步骤之间的关系来求解。现在设报数的值为m，设当环大小为n时，f(n)为最后活下来的人，当环大小为n-1时，f(n-1)为最后活下来的人.........当环大小为1时，f(1)为最后活下来的人。现在已知f(1) = 1，我们只需要找到f(n)和f(n-1)的关系，就可推导出该问题的解。关系如图：
通过关系图我们可以得出
有了f(n)和f(n-1)的关系式，在f(1)已知的情况下，问题就非常简单了。
递归求存活节点
public int getSurvivePosition(int m, int n) {
if (n == 1) {
return n;
}
return (getSurvivePosition(m, n - 1) + m - 1) % n + 1;
}
迭代求存活节点
public int getSurvivePosition(int m, int n) {
int[] dp = new int[n];
dp[0] = 1;
int i = 1;
while (i < n) {
dp[i] = (dp[i - 1] + m - 1) % (i + 1) + 1;
i++;
}
return dp[n - 1];
}
已知节点位置删除
/**
* O(N)解
*/
public Node josephusProblem(Node head, int m) {
if (head == null || head.next == null || m < 1) {
return head;
}
Node cur = head;
int n = 1;
while (cur.next != head) {
n++;
cur = cur.next;
}
int survive = getSurvivePosition2(m, n);
while (survive-- > 1) {
head = head.next;
}
return head;
}
