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