约瑟夫问题

本文参考 leetcode大神题解，查看原文

首先我们来了解下，什么是约瑟夫问题？

这个问题是以弗拉维奥·约瑟夫命名的，他是1世纪的一名犹太历史学家。他在自己的日记中写道，他和他的40个战友被罗马军队包围在洞中。他们讨论是自杀还是被俘，最终决定自杀，并以抽签的方式决定谁杀掉谁。约瑟夫斯和另外一个人是最后两个留下的人。约瑟夫斯说服了那个人，他们将向罗马军队投降，不再自杀。约瑟夫斯把他的存活归因于运气或天意，他不知道是哪一个。 —— 【约瑟夫问题】维基百科

约瑟夫问题与单向循环链表

• 首次看到 约瑟夫问题 是在学习单向循环链表的应用。
• 我们从 链表的header 开始遍历链表。 遍历到第 3 个时，删除。
• 继续从第4个开始遍历，遍历到 第 6 个时，删除。
• 再从第 7 个开始遍历, 遍历到第 9 个时，删除。
• …
• 依次执行上述操作
• 直到链表剩余 1 个元素

以上，就是我之前理解的约瑟夫问题。 接下来，我们看一道约瑟夫问题的题目。

剑指 Offer 62. 圆圈中最后剩下的数字

0,1,,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。

例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

示例 1：

输入: n = 5, m = 3 输出: 3 示例 2：

输入: n = 10, m = 17 输出: 2

限制：

1 <= n <= 10^5 1 <= m <= 10^6

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解 :

• 看到这个题目，想一想，这不是跟我们的 约瑟夫问题 一模一样？
• 只不过相当于，原问题中，m是固定的 3， 而此题目中，m是一个变量。
• 迫不及待使用 单向循环链表 来解题试试咯。

思路一 ： 单向循环链表

• 我们创建一个 node 内部类来存放链表的节点
• 第一步，我们循环创建链表
  • 将 [0, n-1] 范围内的数字，都保存在 node 中，串成 单向循环链表
• 第二部，遍历链表
  • 遍历了 m 个时，将 当前节点 删除
  • 并且，从下一个节点继续遍历
  • 循环退出条件，链表中只有一个元素，也就是 head.next == head
• 最终返回 head.val

代码如下 :

 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

		/**
     *
     *
     * 这道题最常见的解决思路是 单向循环链表
     *
     * 从链表头节点开始遍历，遍历到第 3 个时，删除。并且从第4个接着遍历
     *
     *
     * 下标这种解法，使用链表解决，超时了...
     *
     * 此题目中  n,m的取值范围分别是 :
     *         1 <= n <= 10^5
     *         1 <= m <= 10^6
     *
     *
     * 我们从 m开始删除节点，最终剩下1个节点。需要删除 m-1 次
     * 而每次查找，删除的节点，需要 n 次的查找
     * 所以整体时间复杂度 : O(m * n)
     *
     * 极限情况，会 new 10^5 个 node 节点，循环 10 ^ 6次
     * 好无疑问，耗时会很长
     *
     *
     * */
    public int lastRemaining1(int n, int m) {
        if (n == 0) return 0;
        if (m == 1) return n-1;
        Node head = new Node(0);
        Node node = head;
        for (int i = 1; i < n; i++) {
            node.next = new Node(i);
            node = node.next;
        }
        node.next = head;

        Node current = head;
        while(head.next != head){
            for(int i = 1; i < m; i++){
                current = head;
                head = head.next;
            }
            current.next = current.next.next;
            head = current.next;
        }

        return head.val;
    }

复杂度分析 :

代码提交后，超时。 所以这里我们来分析一下，算法的时间复杂度.

• 经过了 n - 1次的删除操作
• 每次删除操作，需要 m 次的查找，找到要删除的节点
• 所以算法时间复杂度 : O(m * n)
• 这道题中 n, m 的取值范围分别为:
  • 1 <= n <= 10^5
  • 1 <= m <= 10^6
• m * n 的时间复杂度，无疑是非常高的.

思路二 : 数组

• 我们来简单分析下，使用数组来解决问题的时间复杂度

• 也需要经过 n - 1 次的删除操作

• 数组删除元素，复杂度为 O(n), 因为后续所有元素都需要向前移动

• 而数组的每次查找，要删除的位置，是可以通过下标直接访问的，时间复杂度是 O(1)

• 这样看起来，貌似使用数组的时间复杂度 和 m 无关 。 为 O(N ^ 2)

• 但是重点来了！其实是内存连续空间的拷贝的！所以相比于 LinkedList 大量非连续性地址访问，ArrayList 的性能是很 OK 的！

• 以下是， Java数组的删除操作。

  1 2 3 4 5 6 7 8 9 10 11

  /** * Private remove method that skips bounds checking and does not * return the value removed. */ private void fastRemove(Object[] es, int i) { modCount++; final int newSize; if ((newSize = size - 1) > i) System.arraycopy(es, i + 1, es, i, newSize - i); es[size = newSize] = null; }

基于数组模拟链表的实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

public int lastRemaining(int n, int m) {
    if (n == 0) return 0;
    if (m == 1) return n-1;

    ArrayList<Integer> list = new ArrayList<>(n);
    for (int i = 0; i < n; i++) {
        list.add(i);
    }
    int idx = 0;
  	// 删除直到 数组中只有 一个元素
    while (n > 1) {
      	// 找到要删除的位置
        idx = (idx + m - 1) % n;
      	// 删除 
        list.remove(idx);
      	// 删除以后，数组元素 - 1
        n--;
    }
    return list.get(0);
}

提交后，算法通过了。 但是耗时较长，见图。

思路三 : 数学

• 第一轮, [0, 1,2,3,4] 删除第三个，也就是 2 被删除了

• 第二轮, 数组变为 [3,4, 0, 1], 删除第三个，也就是 0 被删除了

• 第三轮, 数组变为 [1,3,4], 删除第三个， 也就是 4 被删除了

• 第四轮, 数组变为 [1,3], 删除第三个，也就是 1 被删除了

• 数组中最后剩余 [3]. 在数组中下标为 0.

• 接下来，我们依次往上推 [3] 在 第四轮，第三轮， 第二轮，第一轮中的下标

• 当我们推导到第一轮时, 也就求出来了，3在数组中的下标

• 我们知道 3 在最后一轮的下标一定是0.

• 所以在 第四轮 剩余2个元素时的下标为 index = (0 + 3) % 2 = 1

• 第三轮 剩余3个元素时的下标为 index = (1 + 3) % 3 = 1

• 第二轮 剩余4个元素时的下标为 index = (1 + 3) % 4 = 0

• 第一轮 在原数组中的下标为 index = (0 + 3) % 5 = 3

• 这样，我们就推导出了，最终结果 3

• 思路明白以后，代码就很简单了

代码如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

/**
 *
 * 数学解法
 *
 * */
public int lastRemaining2(int n, int m) {
    if (n == 0) return 0;
    if (m == 1) return n-1;
    
    int res = 0;
    // 最后一轮剩下2个人，所以从2开始反推
    for (int i = 2; i < n; i++) {
        res = (res + m) % i;
    }
    return res;
}

复杂度分析 :

时间复杂度 : O(N)

空间复杂度 : O(1)

参考文献 :

Java解决约瑟夫环问题，告诉你为什么模拟会超时！