100个小孩手拉手围成一圈，从第1个小孩开始报数，数到3出列，下一个小孩继续从1开始报数，循环报数，求最后留在队列中的小孩的位置。
这是一道非常经典的算法题，我在面试的时候经常提到这道题。这道题是完全可以通过正向思维解答的，但遗憾的是，在所有面试的人中，几乎没有一个人可以正确地解答这道题。
那么，到底要如何解答这道题呢，我们一起来试试看！
解法一：生死看淡，不服就干
首先，我们尝试用正向思维解答，我们用一个集合模拟100个人，集合中的值记录的是原来队列中人物的索引（从0开始）。为了保证函数的通用性，我们用n表示队列中的人数，m表示出列的位置：
本篇文章我们使用Java语言进行讲解，如果你想看其它语言的实现，请在微信公众号”欧阳锋工作室“给我留言
public static int f(int n, int m) {
// 这里用一个集合模拟队列
List<Integer> list = new ArrayList<>();
for (int i = 0; i < n; i ++) {
list.add(i);
}
// 计数器，记录报数序号
int count = 0;
// 当前循环的队列位置索引
int index = 0;
while (list.size() > 1) {
count ++;
// 这里还要注意一个问题，如果报数来到了队列尾部，我们需要从第一个人继续往下报数
// 因此这里的索引计数器需要归0
if (index >= list.size()) {
index = 0;
}
// 接下来开始循环报数，将序号为m的人移出队列
if (count >= m) {
// 移出队列，同时计数器归0
list.remove(index);
count = 0;
}
index ++;
}
return list.get(0);
}
以上这种解法是最容易被想到的方法，问题是：这样做正确吗？
很显然不对！这里忽略了一个问题，一旦队列中有人被移出队列，队列的索引就会发生变化。举个例子，假设第3个人被移除，正常来说，下一个人的索引应该是4。而实际上，这个人的索引依然是3，因为索引计数是连续的。被移除的人索引也会消失，后面所有人的索引都会往前移动一位。
这是上述解法最容易出现的问题，知道了问题的根源，我们将代码继续改进。
我们在上述代码的第28行后面增加一行代码，人物出列后主动将索引值减一：
// 接下来开始循环报数，将序号为m的人移出队列
if (count >= m) {
// 移出队列，同时计数器归0
list.remove(index);
count = 0;
// 这里的索引要减1
index --;
}
修改后，我们尝试运行以上代码，将100与3的值传入到函数中，运行得到结果90，答案是正确的。
解法二：死生不惧，一往直前
直给的解题方式，除了上述解法之外，还有一种常见的解法，就是不管三七二十一，一路循环，直至输出结果。
这种解法同样需要构建用户队列，只是队列的形式发生了变化，我们使用一个长度为n的Boolean数组构建用户队列。
这种解法的完整代码如下：
public static int f(int n, int m) {
Boolean[] arr = new Boolean[n];
for (int i = 0; i < arr.length; i ++) {
arr[i] = true;
}
// 队列中还剩余的人数
int leftCount = arr.length;
// 计数器，记录报数序号
int count = 0;
// 当前循环的队列位置索引
int index = 0;
while (leftCount > 1) {
if (arr[index]) {
count++;
}
if (count == m) {
arr[index] = false;
count = 0;
leftCount --;
}
index ++;
// 这里同样需要处理计数到达队列尾部的情况
if (index >= n) {
index = 0;
}
}
int result = 0;
for (int i = 0; i < arr.length; i ++) {
if (arr[i]) {
result = i;
break;
}
}
return result;
}
这种解法相对于第一种解法来说，时间复杂度更高，循环次数更多，循环次数差不多是第一种解法的3到5倍，甚至更多。但相对第一种解法，这种解法更容易被人接受，也无需考虑索引的变化。在面试中，如果你想不到任何一种解法，我推荐你使用这种解法。
解法三：巧用链表，场景还原
分析考题，我们不难发现，这似乎是我们非常熟悉的链表结构。在第三种解法中，我们尝试使用链表模拟这个用户队列，看看能否带给我们一些惊喜。
由于始终使用单向报数，我们就用一个单向链表来模拟这个数据结构：
// 这里用Child类来模拟每一个参与的小孩，其中的value值保存的是当前用户的索引
public class Child {
// 简单起见，这里我们全部使用public
public Child next;
public int value;
public Child(int value) {
this.value = value;
}
}
public static int f(int n, int m) {
Child head = new Child(0);
Child current = head;
for (int i = 1; i < n; i ++) {
Child child = new Child(i);
current.next = child;
current = child;
}
// 为了构建首尾相接的链表，这里我们主动将尾节点与头结点连接起来
// 当前节点恰好指向尾节点
current.next = head;
// 接下来再移动一次指针，让current指向头节点
// 为了方便获取前一个节点，这里我们用一个变量表示前一个节点
Child prev = current;
current = current.next;
// 定义计数器
int count = 0;
// 一旦收尾相接，当前节点指向了自身，证明队列中只有一个用户了，跳出循环，游戏结束
while (current.next != current) {
count ++;
if (count == m) {
prev.next = current.next;
count = 0;
}
prev = current;
current = current.next;
}
return current.value;
}
以上就是这种解法的完整代码，代码中包含了每一行代码的详细解释。在这个解法中，我们利用链表模拟了人物队列，通过控制当前用户的指针移动来模拟报数。最终，当用户的下一个用户指针指向自己的时候跳出循环，游戏结束，当前用户就是队列中剩余的最后一个用户。
这种解法相对于上面两种解法来说更容易理解，并且这种解法的时间复杂度不高，循环次数与第一个解法的循环次数一致。目前来说，他是在所有的解法中是最优的。
那么，是否还有更好的解法呢？
解法四：数学大法，九九归一
计算机科学离不开数学！最后，我们一起来试试看，尝试利用数学的武器更加巧妙地解决这个问题。由于这是一个规律性的动作，我们可以肯定，这应该有一个固定的数学规律。
但现在的问题是，如何找到这个规律呢？这似乎不太容易。
这里我们先假设总人数为n，报数为m的人出列，用f(n, m)表示最终留在队列中的人的位置。
为了便于大家理解，我们先来看一个实际的例子，假设n=5, m=3, 即队列中只有5个人，报数为3的人出列。
第一轮报数，位置为3的人出列
[1, 2, x, 4, 5]
出列后，从4开始报数，我们将开始报数的人挪到第一位，剩下的人按照报数的顺序往后排，得到一个新的队列：
[4, 5, 1, 2]
从这里，我们开始第二轮报数，这一轮报数位置为1的人出列
[4, 5, x, 2]
我们继续按照上面的方式，转换队列，重新第三轮报数：
[2, 4, 5] => [2, 4, x]
第四轮：
[2, 4] => [x, 4]
第五轮：
[4]
以上就是n = 5, m = 3的情况下完整的报数情况，接下来我们仅关注第一次报数发生的变化。
第一轮报数完成后，队列由[1, 2, 3, 4, 5]转换成了[4, 5, 2, 1]。
- 队列一：[1, 2, 3, 4, 5]
- 队列二：[4, 5, 1, 2]
注意看，如果我们不去关注队列中人物的位置，仅关注队列本身。这两个队列有什么关系？
- 两个队列都是从1开始报数
- 两个队列人数仅仅相差1
这里很微妙，这其实可以看做数量为5的人物队列，与数量为4的人物队列。如果我们用Q表示队列的话，第一个队列可以用Q(5)表示，第二个队列可以用Q(4)来表示，Q(4)实际上是Q(5)的子队列。
在这两个队列中，还有两个干扰项 [1, 2], 为了排除干扰，我们将他们改成 [6, 7], 即：
- 队列一：[1, 2, 3, 4, 5]
- 队列二：[4, 5, 6, 7]
这个时候队列Q(5)与Q(4)产生了一定的关系，同等位置处的索引值恰好相差3（其实就是m的值，为什么是m呢？大家可以自行思考一下）。
接下来，我们关注第二个队列的第一轮报数，报数为3的人出列，也就是队列二中的6。那么，TA在原来队列中的位置到底是什么呢？答案是1，实际就是将6 % 5进行取模得到的值。
这里似乎有一个固定的规律，即：假设队列2第一轮报数出列的人在队列2中的位置是x2, 在队列1中的位置是x1, x2与x1应该存在下面这个关系：
x1 = (x2 + 3) % 5
第一轮报数等式成立，那么第二轮报数是否成立呢？一直到剩余最后一个人是否成立呢？答案是：当然成立。
由此，我们可以猜测f(n, m)与f(n, m - 1)存在下面这样的关系：
f(n, m) = (f(n - 1, m) + m) % n
为了加深大家的理解，我们将转换过程用图片再一次展示给大家看：
以上就是队列长度为n，第一次报数为m的用户出列后将n-1的其他人转换到n-1的子队列的过程。
由此可以得出结论，这里的转换是普适的，以上的公式适用于所有情况。
上述公式中，我们没有考虑当前队列中只有一个人的情况，这里我们将其补全，得到下面的递推公式：
f(n, m) = 0 (n = 1)
f(n, m) = (f(n - 1, m) + m) % n (n > 1)
得到上述递推公式之后，问题就变得简单了：
public static int f(int n, int m) {
if (n == 1) return 0;
return (f(n - 1, m) + m) % n;
}
换成三目运算符，我们甚至可以使用一行代码解答这个问题：
public static int f(int n, int m) {
return n == 1 ? 0 : (f(n - 1, m) + m) % n;
}
最佳实践
以上就是”约瑟夫环问题“的常见几种解法，算法效率最高的解法是第四种，其次是第一种与第三种，第二种解法效率最差，但最容易想到。尽管通过数学归纳法可以最高效地解答这个问题，但我仍然推荐第三种解法，这种解法最符合计算机思维。同时，算法复杂度也不高。但如果在高度要求性能的程序中，当然毫无疑问，解法四是你的最优选择。
总结
在这个问题解答的过程中，我们用到了链表，链表是一种非常常见的数据结构。可能你经常在用，但并不了解。链表问题经常出现在算法中，如果你希望对链表进一步深入了解，请关注公众号”欧阳锋工作室“，下一篇文章我们讲一讲与链表相关的那些算法题。
