jz062.圆圈中最后剩下的数字

题目链接

本题就是著名的约瑟夫环问题，我们介绍两种解题方法，一种是用环形链表模拟圆圈的经典解法；第二种是分析每次被删除的数字的规律并直接计算出圆圈中最后剩下的数字。对于第一种方法，我们用一个数据结构如环形链表来模拟这个圆圈，我们可以创建一个共有n个节点的环形链表，然后每次在这个链表中删除第m个节点。如果我们用一两个例子仔细分析上述代码的运行过程，就会发现，实际上需要在环形链表里重复遍历很多遍。重复的遍历当然对时间效率有负面影响。这种方法每删除一个数字需要m步运算，共有n个数字，因此总的时间复杂度为O（MN），同时这种思路需要有一个辅助链表来模拟圆圈，其空间复杂度为O（N）。

第二种方法相对更加高效。首先，我们先定义一个关于n和m的方程f(n, m)，表示每次在n个数字0，1，… ，n-1中删除第m个数字最后剩下的数字。在这n个数字中，第一个被删除的数字是(m-1)%n（之所以是m-1是因为起点的数字也会被算进去）。为了简单，我们把(m-1)%n记为k，那么删除k之后剩下的n-1个数字为0, 1, … , k-1, k+1, … , n-1，并且下一次删除的数字从k+1开始计数。相当于在剩下的序列中，k+1排在最前面，从而形成k+1, …, n-1, 0, 1, …, k-1。该序列最后剩下的数字也应该是关于n和m的函数。由于这个序列的规律和前面最初的序列不一样（最初的序列是从0开始的连续序列），因此该函数不同于前面的函数，记为f（n-1，m）。最初序列最后剩下的数字f’（n，m）一定是删除一个数字后的序列最后剩下的数字，即f（n，m）= f‘（n-1，m）。接下来我们把剩下的这n-1个数字的序列k+1，…, n-1, 0, 1, …, k-1进行映射，映射的结果是形成一个0-n-2的序列。

k+1 –> 0

k+2 –> 1

…

n-1 –> n-k-2

0 –> n-k-1

1 –> n-k

…

k-1 –> n-2

我们把映射定义为p，则p（x）=（x-k-1）%n。它表示如果映射前的数字是x，那么映射之后的数字是（x-k-1）%n。该映射的逆映射是$p^{-1}(x)=(x+k+1)%n$。由于映射后的序列和最初的序列具有相同的形式，即都是从0开始的连续序列，因此仍然可以用函数f来表示，记为f（n-1，m）。根据我们的映射规则，映射之前的序列中最后剩下的数字f‘（n-1，m）=$p^{-1}[f(n-1,m)]$=[f(n-1, m)+k+1]%n，把k=（m-1）%n代入得到f（n，m）=f‘（n-1，m）=[f(n-1, m)+m]%n。因此我们得到了一个递推公式。要得到n个数字的序列中最后剩下的数字，只需要得到一个n-1个数字的序列中最后剩下的数字，并以此类推。当n=1时，也就是序列中开始只有一个数字0，那么很显然最后剩下的数字就是0。我们把这种关系表示为：

如上公式无论是用递归还是循环都很容易实现，如下是基于循环实现的代码。这个算法的时间复杂度是O（N），空间复杂度是O（1）。

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