leetcode之约瑟夫环问题，妙哉公式法

约瑟夫环问题，妙哉公式法"/>

leetcode之约瑟夫环问题，妙哉公式法

约瑟夫环问题

约瑟夫环问题是N个人围成一圈，从第一个人开始报数，报到m的人出圈，剩下的人继续从1开始报数，报到m的人出圈；如此往复，直到最后只剩下1个人。而今天的leetcode面试题62. 圆圈中最后剩下的数字正是约瑟夫环问题，题目如下。

思路一：循环链表法

在我们学习基础的数据结构时，循环链表可谓是专为约瑟夫环问题而生，其实这是该问题的暴力法版本，我们用一个循环链表存储题目中的N个人，然后开始删除第M%N个人，循环往复直到剩下最后一个人即可。

时间复杂度为O(NM)，性能较差。并且考虑到golang中没有现成的链表结构可供使用，所以多少还是不方便答题。

思路二：公式法

由于需要环状结构，我们使用数组展示时，会在M>N时，展示多个复制的数组以表示环状。以[0,1,2,3,4]举例，M为3。

第一轮 [0 1 《2》3 4][0 1 2 3 4]
第二轮 [3 4 《0》1][3 4 0 1]
第三轮 [1 3 《4][1 3 4]
第四轮 [1 3][《1》3]
第五轮 [3]

其中《》中的数字为每次被删除的数字。
最后剩下的数字3下标是0。那么我们从后往前推一下。

第四轮时，补上m个位置，数组大小是2，那么3对应的下标是(0+3)%2 = 1
第三轮时，补上m个位置，数组大小是3，那么3对应的下标是(1+3)%3 = 1
第二轮时，补上m个位置，数组大小是4，那么3对应的下标是(1+3)%4 = 0
第一轮时，补上m个位置，数组大小是5，那么3对应的下标是(0+3)%5 = 3

由此我们可以得出反推的公式

f(n,m)表示数组大小为n时，每次剔除第m个元素后剩下的那一个元素的序号。
f(n,m) = (f(n-1,m) + m) % n

至于实现的方式，我们可以从n到0使用递归，也可以从2（举例中的数组大小为2开始）到n，使用迭代。

使用迭代的复杂度如下：
时间复杂度：O(n)，需要求解的函数值有 n 个。
空间复杂度：O(1)，只使用常数个变量。
使用递归时间复杂度跟迭代一样，但是空间复杂度为O(n)。

leetcode题目

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

来源：力扣（LeetCode）
链接：
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

Go版本代码

func lastRemaining(n int, m int) int {var ans int//使用迭代法实现for i:=2;i<=n;i++ {ans = (ans+m)%i}return ans
}

总结

1 好的数据结构能解决数据的存储问题，但是不一定能有好的性能。
2 算法的终极是数学，遇题多思考，多总结。怕什么真理无穷，进一寸有一寸的欢喜。