深入理解约瑟夫环 – 把握递推思想

读者可能会有疑惑：约瑟夫环递推时，是怎么像模拟法那样跳过已删除位置的？本文着重讲解约瑟夫环规律推导和递推思想规避跳步原因，如果帮助到读者加深理解欢迎留言，如有错误欢迎讨论，转载请注明出处

问题抽象 – 明确约瑟夫环问题目的

0…N-1 共N个元素围成环，从0开始计数，每计数到M删除并重新计数，求N-1轮后剩余元素。即约瑟夫环问题的目的是求得 剩余元素下标 对应 原序列的哪个下标，若想找到数学规律，容易想到后文两种分析思路

问题分析 – 寻求下标与原序列直接对应关系

求解思路

因为每一轮都要对应到原序列，这就意味着 前进量M需要跳过M个未删除项，这就需要考虑到原序列中已删除的位置：前进量是否囊括删除项？囊括几个删除项？通项公式非常不容易分析。寻找下标与原序列直接对应关系实际还是模拟法，循环链表模拟，时间 \scriptsize O(MN)，空间 \scriptsize O(N)

实现代码

class Solution {
    class ListNode {
        int id;
        ListNode prev;
        ListNode next;

        public ListNode(int id, ListNode prev, ListNode next) {
            this.id = id;
            this.next = next;
            this.prev = prev;
        }
    }

    class LinkedList {
        ListNode head;
        ListNode tail;
        int size;

        public LinkedList() {
            head = new ListNode(-2, null, null);
            tail = new ListNode(-1, head, null);
            head.next = tail;
        }

        public void addLast(ListNode node) {
            node.prev = tail.prev;
            tail.prev.next = node;
            tail.prev = node;
            node.next = tail;
            size++;
        }

        public void removeNode(ListNode node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
            node = null; // help GC
            size--;
        }
    }

    public int lastRemaining(int N, int M) {
        LinkedList list = new LinkedList();
        for (int i = 0; i < N; i++) {
            list.addLast(new ListNode(i, null, null));
        }

        ListNode node = list.head;
        while (list.size > 1) {
            for (int i = 0; i < M; i++) {
                node = node.next;
                if (node == list.tail)
                    node = list.head.next;
            }
            list.removeNode(node);
        }

        return list.head.next.id;
    }
}

上述过程中间隔元素没必要访问，直接使用下标计算可以减少成本，注意删除元素操作带来的问题：①数组长度发生变化 ②当前指针指向了下一元素，再过M-1项为才是下一个正确删除位置。此方法已经非常接近递推方法，时间 \scriptsize O(N)，空间 \scriptsize O(N)

public int lastRemaining(int N, int M) {
    List<Integer> list = new LinkedList<>();
    for (int i = 0; i < N; i++) {
        list.add(i);
    }

    for (int i = N, pos = 0; i > 1; i--) {
        list.remove(pos = (pos + M - 1) % i);
    }

    return list.get(0);
}

问题分析 – 寻求下标与上轮下标的对应关系

求解思路

注意到每次操作是相同的，相邻轮之间就可能存在递推关系。删除元素后的新一轮从0开始重新计数，我们把新计数作为元素在新一轮的虚构下标。剩余元素最终下标一定是0，若存在递推关系依次递推回初始轮即可得知剩余元素的初始下标

从直观过程来寻找规律，取N=5、M=3：正向模拟一轮删除重新计数，相当于数组循环左移M位后再删除末尾元素，如下图所示

id(x)为第x轮的下标，N(x)为第x轮的数组长度，则递推回上一轮的公式为

\scriptsize
id(x) =
\left \{
\begin{array}{ll}
(id(x+1) + M) \mod N(x), & x \ge 0\\
0,   & x=N-1\\
\end{array}
\right.

从两轮的下标来归纳映射关系，递推回上一轮的公式同上。亲自动手才能找到共性，两种方法均找到了相邻轮之间的递推关系，时间 \scriptsize O(N)，空间 \scriptsize O(1)

现在来解答文章导言提出的问题：
其一 两轮虚构下标关系的推导只限用于留存元素，不考虑两轮之间的删除元素，不涉及删除元素的推导
其二 虚构下标关系是相邻轮之间的映射，不是每一轮实际坐标与原序列的映射，与原序列坐标无关，不需考虑原序列中删除的元素
其三 两轮之间仅删除单个元素，且下标均如下图中的 \scriptsize (M-1)\mod N(x)，规避了不同轮中已删元素数量位置不同的麻烦，将变化转为确定，统一了规律

实现代码

public int lastRemaining(int N, int M) {
    int id = 0;
    for (int Nx = 2; Nx <= N; Nx++) {
        id = (id + M) % Nx;
    }
    return id;
}