Question

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

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

图6.2　由0－4这5个数字组成的圆圈

本题就是有名的约瑟夫（Josephuse）环问题。我们介绍两种方法：一种方法是用环形链表模拟圆圈的经典解法，第二种方法是分析每次被删除的数字的规律并直接计算出圆圈中最后剩下的数字。

经典的解法，用环形链表模拟圆圈

既然题目中有一个数字圆圈，很自然的想法就是用一个数据结构来模拟这个圆圈。在常用的数据结构中，我们很容易想到环形链表。我们可以创建一个总共有n个结点的环形链表，然后每次在这个链表中删除第m个结点。

如果面试官要求我们不能使用标准模板库里的数据容器来模拟环形链表，我们自己实现一个链表也不是很难的事情。如果面试官没有特殊要求，我们就可以用模板库中的std::list来模拟一个环形链表。由于std::list本身并不是一个环形结构，因此每当迭代器（Iterator）扫描到链表末尾的时候，我们要记得把迭代器移到链表的头部，这样就相当于按照顺序在一个圆圈里遍历了。这种思路的代码如下：

如果我们用一两个例子仔细分析上述代码的运行过程，就会发现我们实际上需要在环形链表里重复遍历很多遍。重复的遍历当然对时间效率有负面的影响。这种方法每删除一个数字需要m步运算，总共有n个数字，因此总的时间复杂度是O（mn）。同时这种思路还需要一个辅助链表来模拟圆圈，其空间复杂度是O（n）。接下来我们试着找到每次被删除的数字有哪些规律，希望能够找到更加高效的算法。

创新的解法，拿到Offer不在话下

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

在这n个数字中，第一个被删除的数字是（m－1）%n。为了简单起见，我们把（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的序列：

我们把映射定义为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），因此无论在时间效率还是空间效率上都优于第一种方法。

源代码：

本题完整的源代码详见45_LastNumberInCircle项目。

测试用例：

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

- 特殊输入测试（圆圈中有0个数字）。

- 性能测试（从最初有4000个数字的圆圈中每次删除第997个数字）。

本题考点：

- 考查抽象建模的能力。不管应聘者是用环形链表来模拟圆圈，还是分析被删除数字的规律，都要深刻理解这个问题的特点并编程实现自己的解决方案。

- 考查对环形链表的理解及应用能力。大部分面试官只要求应聘者基于环形链表的方法解决这个问题。

- 考查数学功底及逻辑思维能力。少数对算法和数学基础要求很高的公司，面试官会要求应聘者不能使用O（n）的辅助内存，这个时候应聘者就只能静下心来一步步推导出每次删除的数字有哪些规律。