本题就是有名的约瑟夫（Josephuse）环问题，此题的难点在于求解状态转移方程。

Question

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\)

测试用例

功能测试（输入的m小于n，比如从最初有5个数字的圆圈中每次删除第2、3个数字；输入的m大于或者等于n，比如从最初有6个数字的圆圈中每次删除第6、7个数字）。 特殊输入（圆圈中有0个数字）。 性能测试（从最初有4000个数字的圆圈中每次删除第997个数字）。

本题考点

考查应聘者的抽象建模能力。不管应聘者是用环形链表来模拟圆圈，还是分析被删除数字的规律，都要深刻理解这个问题的特点并编程实现自己的解决方案。 考查应聘者对环形链表的理解及应用能力。大部分面试官只要求应聘者基于环形链表的方法解决这个问题。 考查应聘者的数学功底及逻辑思维能力。少数对算法和数学基础要求很高的公司，面试官会要求应聘者不能使用\(O(n)\) 的辅助内存，这时候应聘者就只能静下心来一步步推导出每次删除的数字有哪些规律。

Intuition

用链表模拟环

算法 很容易想到用环形链表来模拟环。我们可以创建一个共有 \(n\) 个节点的环形链表，然后每次在这个链表中删除第 \(m\) 个节点。 由于链表本身并不是一个环形结构，因此每当迭代器（lterator）扫描到链表末尾的时候，我们要记得把迭代器移到链表的头部，这样就相当于按照顺序在一个圆圈里遍历了。

复杂度分析 时间复杂度：\(O(n \times m)\) ； 空间复杂度：\(O(n)\)；
由于复杂度太高，无法通过LeetCode所有测试用例。

分析规律

表格找规律

约瑟夫问题比较难想的点有两个：

• 当数到最后一个结点不足m个时，需要跳到第一个结点继续数。
• 每轮都是上一轮被删结点的下一个结点开始数 m 个。

第一点比较好解决，可以通过取余来完成。 第二点的解决方案是：将删除结点的后继作为下一轮的第一个结点，后续结点依次排列。这样每轮都是从首结点开始数 m 个了。

以输入n=7 个节点，每次从这个圆圈里删除第 m=9个数字为例。

轮次	当前序列	原起点	删除数值	新起点
1	0, 1, 2, 3, 4, 5, 6	0	9%7=2，以0为第一个数，第2个数为1，删除1。	2
2	0, 2, 3, 4, 5, 6	2	9%6=3，以2为第一个数，第3个数为4，删除4。	5
3	0, 2, 3, 5, 6	5	9%5=4，以5为第一个数，第4个数为2，删除2。	3
4	0, 3, 5, 6	3	9%4=1，以3为第一个数，第1个数为3，删除3。	5
5	0, 5, 6	5	9%3=0，以5为第一个数，第0个数为0，删除0。	5
6	5, 6	5	9%2=1，以5为第一个数，第1个数为5，删除5。	6
7	6	6	只剩一个数，停止删除，返回。	6

由上表可知，删除数之后的那个数为下一轮新的起点，以第一轮为例，删除1，下一个数2就是下一轮起点。

剑指offer原书数学证明

1、首先我们定义一个关于 \(n\) 和 \(m\) 的方程 \(f(n, m)\)，表示每次在 \(n\) 个数字 \(0\), \(1\), …, \(n-1\) 中删除第 \(m\) 个数字最后剩下的数字。

2、第一个被删除的数字是 \(k=(m-1)\%n\)。

3、设新形成的 \(k+1\), \(…\), \(n-1\), \(0\), \(1\), \(…\), \(k-1\) 序列的函数为 \(f'(n-1, m)\)，最初序列最后剩余数字 \(f(n-1, m)\) 一定是删除一个数字之后的序列最后新形成的数字，所以有 \(f'(n-1, m)=f(n-1, m)\)。

4、将新形成的 \(k+1\), \(…\), \(n-1\), \(0\), \(1\), \(…\), \(k-1\) 序列用映射函数 \(p(x)=(x-k-1)\%n\) 映射为 \(0\),\(1\), \(2\), ..., \(n-2\) 的序列。

新序列（\(x\)）	映射序列(（\(p(x)=(x-k-1)\%n\)）
\(k+1\)	\(0\)
\(k+2\)	\(1\)
\(...\)	\(...\)
\(n-1\)	\(n-k-2\)
\(0\)	\(n-k-1\)
\(1\)	\(n-k\)
\(...\)	\(...\)
\(k-1\)	\(n-2\)

可知，逆映射函数 \(p^{-1}(x)=(x+k+1)\%n\)

5、由于映射之后的序列和最初的序列具有同样的形式，即都是从 \(0\) 开始的连续序列，因此仍然可以用函数f来表示，记为 \(f(n-1, m)\)。根据我们的映射规则，映射之前的序列中最后剩下的数字满足以下关系： \[ f(n-1, m)=p^{-1}[(n-1, m)]=[f(n-1, m)+k+1]%n \] 将 \(k=(m-1)\%n\) 代入上式可得： \[ f(n-1, m) = f'(n-1, m) = [f(n-1,m)+m]\%n \]

6、经过上面复杂的分析，我们终于找到了一个递归公式。要得到 \(n\) 个数字的序列中最后剩下的数字，只需要得到 \(n-1\) 个数字的序列中最后剩下的数字，并以此类推。当 \(n=1\) 时，也就是序列中开始只有一个数字0，那么很显然最后剩下的数字就是0。我们把这种关系表示为： \[ f(n, m) = \begin{cases} 0, \quad n=1 \\ [f(n-1,m)+m]\%n, \quad n>1 \end{cases} \] 这个公式无论是用递归还是用循环，都很容易实现。

复杂度分析

时间复杂度：\(O(n)\)；空间复杂度：\(O(1)\)；可以通过LeetCode所有测试用例。

参考链接

作者：Time-Limit 链接：https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/chi-jing-stsu-degd-degtsu-tu-jie-yue-se-fu-huan-hu/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

# Code

用链表模拟环

class Solution:
    def lastRemaining(self, n: int, m: int) -> int:
        # 构建循环链表
        nums = list(range(n))
        dummy = ListNode(None)
        p = dummy
        for num in nums:
            p.next = ListNode(num)
            p = p.next
        
        head = dummy.next
        p.next = head

        # 每隔m-1删除一个节点
        count = n
        # 最开始时 p 指向之前的tail
        while count > 1:
            for _ in range(m-1):
                p = p.next
            _next = p.next.next
            p.next.next = None
            p.next = _next
            # p = p.next
            count -= 1

        p.next = None
        return p.val

分析规律

• 递归写法

class Solution:
    def lastRemaining(self, n: int, m: int) -> int:
        def cur(n, m):
            if n == 1:
                return 0
            return (cur(n-1, m) + m) % n

        return cur(n, m)

• 上面的递归可以改写为迭代，避免递归使用栈空间。

class Solution:
    def lastRemaining(self, n: int, m: int) -> int:
        if n < 1 or m < 1:
            return -1
        last = 0
        for i in range(1, n+1):
            last = (last + m) % i
        return last